Submission #440943

#	Time	Username	Problem	Language	Result	Execution time	Memory
440943		ogibogi2004	Distributing Candies (IOI21_candies)	C++17	0 / 100	157 ms	39620 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=1e9;
ll m;
struct node
{
	int max1;
	int max2;
	bool nomax2,nomin2;
	int min1;
	int min2;
	int toAdd;
	int maxx()
	{
		int ret=max1;
		if(!nomax2)ret=max(ret,max2);
		ret=max(ret,min1);
		if(!nomin2)
		{
			ret=max(ret,min2);
		}
		return ret;
	}
};
int t=0;
node tree[4*MAXN];
node merge(node n1,node n2)
{
	node ret;
	set<int>maxes;
	maxes.insert(n1.max1+n1.toAdd);
	maxes.insert(n1.max2+n1.toAdd);
	maxes.insert(n2.max1+n2.toAdd);
	maxes.insert(n2.max2+n2.toAdd);
	set<int>mins;
	mins.insert(n1.min1+n1.toAdd);
	mins.insert(n1.min2+n1.toAdd);
	mins.insert(n2.min1+n2.toAdd);
	mins.insert(n2.min2+n2.toAdd);
	ret.toAdd=0;
	ret.min1=(*mins.begin());
	mins.erase(mins.begin());
	if(mins.size()>0)ret.min2=(*mins.begin());
	else {ret.min2=+INF;ret.nomin2=1;}
	ret.max1=(*maxes.rbegin());
	maxes.erase((*maxes.rbegin()));
	if(maxes.size()>0)ret.max2=(*maxes.rbegin());
	else {ret.max2=-INF;ret.nomax2=1;}
	return ret;
}
void build(int l,int r,int idx)
{
	if(l==r)
	{
		tree[idx].max1=tree[idx].min1=0;
		tree[idx].max2=0;
		tree[idx].min2=m;
		tree[idx].nomax2=1;
		tree[idx].nomin2=1;
		tree[idx].toAdd=0;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,idx*2);
	build(mid+1,r,idx*2+1);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void push(int l,int r,int idx)
{
	tree[idx].max1+=tree[idx].toAdd;
	tree[idx].max2+=tree[idx].toAdd;
	tree[idx].min1+=tree[idx].toAdd;
	tree[idx].min2+=tree[idx].toAdd;
	if(l!=r)
	{
		tree[idx*2].toAdd+=tree[idx].toAdd;
		tree[idx*2+1].toAdd+=tree[idx].toAdd;
		tree[idx*2].max1=min(tree[idx*2].max1,tree[idx].max1-tree[idx*2].toAdd);
		tree[idx*2+1].max1=min(tree[idx*2+1].max1,tree[idx].max1-tree[idx*2+1].toAdd);
		tree[idx*2].min1=max(tree[idx*2].min1,tree[idx].min1-tree[idx*2].toAdd);
		tree[idx*2+1].min1=max(tree[idx*2+1].min1,tree[idx].min1-tree[idx*2+1].toAdd);
	}
	tree[idx].toAdd=0;
}
void minWithSafe(int l,int r,int idx,int val)
{
	tree[idx].max1=min(tree[idx].max1,val-tree[idx].toAdd);
	push(l,r,idx);
}
void maxWithSafe(int l,int r,int idx,int val)
{
	tree[idx].min1=max(tree[idx].min1,val-tree[idx].toAdd);
	push(l,r,idx);
}
void minWith(int l,int r,int idx,int ql,int qr,int val)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(tree[idx].max1<=val)return;
	if(l>=ql&&r<=qr&&tree[idx].max2<val)
	{
		minWithSafe(l,r,idx,val);
		return;
	}
	int mid=(l+r)/2;
	minWith(l,mid,idx*2,ql,qr,val);
	minWith(mid+1,r,idx*2+1,ql,qr,val);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void maxWith(int l,int r,int idx,int ql,int qr,int val)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(tree[idx].min1>=val)return;
	if(l>=ql&&r<=qr&&tree[idx].min2>val)
	{
		maxWithSafe(l,r,idx,val);
		return;
	}
	int mid=(l+r)/2;
	maxWith(l,mid,idx*2,ql,qr,val);
	maxWith(mid+1,r,idx*2+1,ql,qr,val);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void update(int l,int r,int idx,int ql,int qr,int val)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		tree[idx].toAdd+=val;
		push(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update(l,mid,idx*2,ql,qr,val);
	update(mid+1,r,idx*2+1,ql,qr,val);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
	push(l,r,idx);
	if(l>qr)return -INF;
	if(r<ql)return -INF;
	if(l>=ql&&r<=qr)return tree[idx].maxx();
	int mid=(l+r)/2;
	return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    ll n = c.size(),q=l.size();m=c[0];
    vector<int>s(n,0);
    build(1,n,1);
    for(int i=0;i<q;i++)
    {
		l[i]++;r[i]++;
		update(1,n,1,l[i],r[i],v[i]);
		//cout<<i<<" - 1\n";
		//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
		//cout<<endl;
		//cout<<i<<" - 2\n";
		minWith(1,n,1,1,n,c[0]);
		//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
		//cout<<endl;
		//cout<<i<<" - 3\n";
		maxWith(1,n,1,1,n,0);
		//for(int j=0;j<n;j++)cout<<query(1,n,1,j+1,j+1)<<" ";
		//cout<<endl;
	}
	for(int i=0;i<n;i++)
	{
		s[i]=query(1,n,1,i+1,i+1);
	}
	return s;
}

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