Submission #1243506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243506		MuhammadSaram	Distributing Candies (IOI21_candies)	C++20	8 / 100	1041 ms	33456 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 2e5 + 1;
const ll inf = 1e18;

struct node
{
	ll mx, mn, lz;
} seg[M*2];

int q;

void push(int v,int lc,int rc)
{
	ll x=seg[v].lz;
	seg[lc].mn+=x, seg[rc].mn+=x;
	seg[lc].mx+=x, seg[rc].mx+=x;
	seg[lc].lz+=x, seg[rc].lz+=x;
	seg[v].lz=0;
}

node merge(node a,node b)
{
	a.mx=max(a.mx,b.mx);
	a.mn=min(a.mn,b.mn);
	return a;
}

void modify(int l, int r,int x,int v=0,int s=0,int e=q+1)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		seg[v].mn+=x,seg[v].mx+=x,seg[v].lz+=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	push(v, lc, rc);
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=merge(seg[lc],seg[rc]);
	seg[v].lz=0;
}

node get(int l,int r,int v=0,int s=0,int e=q+1)
{
	if (l>=e or r<=s)
		return {0,inf};
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	push(v,lc,rc);
	return merge(get(l,r,lc,s,mid), get(l,r,rc,mid,e));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(); q=l.size();
	vector<int> ad[n], rem[n];
	for (int i=0;i<q;i++)
		ad[l[i]].push_back(i), rem[r[i]].push_back(i);
	vector<int> ans(n);
	for (int i=0;i<n;i++)
	{
		for (int id:ad[i])
			modify(id+1,q+1,v[id]);
		int s=-1, e=q;
		while (s+1<e)
		{
			int mid=(s+e)/2;
			node a=get(mid,q+1);
			if (a.mx-a.mn<=c[i])
				e=mid;
			else
				s=mid;
		}
		if (e==0)
		{
			node a=get(0,q+1);
			ans[i]=get(q,q+1).mx;
			ans[i]-=a.mn;
		}
		else
		{
			node a=get(e-1,q+1), b=get(e,q+1);
			if (a.mn==b.mn)
				ans[i]=get(q,q+1).mx-b.mn;
			else
				ans[i]=c[i]-b.mx+get(q,q+1).mx;
		}
		for (int id:rem[i])
			modify(id+1,q+1,-v[id]);
	}
	return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33