Submission #435754

#	Time	Username	Problem	Language	Result	Execution time	Memory
435754		mosiashvililuka	Distributing Candies (IOI21_candies)	C++17	29 / 100	831 ms	19956 KiB

candies

#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[200009],tes,t,lef,rig,mid,l,r,z,zz,ans[200009];
pair <pair <int, int>, int> P[200009];
pair <int, int> Q[200009];
pair <int, int> seg[800009];
vector <int> ANS;
void pushdown(int q, int w, int rr){
	if(seg[rr].first==0||seg[rr].first==1){
		seg[rr*2]=seg[rr];seg[rr*2+1]=seg[rr];
	}else{
		seg[rr*2].second+=seg[rr].second;seg[rr*2+1].second+=seg[rr].second;
	}
	seg[rr].first=-1;seg[rr].second=0;
}
void read(int q, int w, int rr){
	if(q==w){
		z=seg[rr].first;zz=seg[rr].second;
		return;
	}
	pushdown(q,w,rr);
	if((q+w)/2>=l){
		read(q,(q+w)/2,rr*2);
	}else{
		read((q+w)/2+1,w,rr*2+1);
	}
}
void upd(int q, int w, int rr){
	if(q!=w) pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		if(q!=w){
			seg[rr].first=z;seg[rr].second=zz;
		}else{
			if(z==0||z==1){
				seg[rr].first=z;seg[rr].second=zz;
			}else{
				seg[rr].second+=zz;
			}
		}
		return;
	}
	upd(q,(q+w)/2,rr*2);
	upd((q+w)/2+1,w,rr*2+1);
}
vector<int> distribute_candies(vector<int> Cc, vector<int> Ll, vector<int> Rr, vector<int> Vv) {
    a=Cc.size();tes=Ll.size();
    for(i=1; i<=a; i++){
    	f[i]=Cc[i-1];
    	Q[i].first=f[i];Q[i].second=i;
	}
	sort(Q+1,Q+a+1);
	for(i=1; i<=a; i++) f[i]=Q[i].first;
	for(t=1; t<=tes; t++){
		P[t].first.first=Ll[t-1];P[t].first.second=Rr[t-1];
		P[t].second=Vv[t-1];
	}
	for(i=0; i<=800002; i++){
		seg[i].first=-1;seg[i].second=0;
	}
	for(t=1; t<=tes; t++){
		lef=0;rig=a+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			l=mid;z=-1;zz=0;
			read(1,a,1);
			if(z==-1){
				zx=zz;
			}
			if(z==0){
				zx=zz;
			}
			if(z==1){
				zx=f[mid]+zz;
			}
			if(zx+P[t].second>=0&&zx+P[t].second<=f[mid]){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		mid=rig;
		if(mid!=1){
			l=1;r=mid-1;
			if(P[t].second>0){
				z=1;zz=0;
			}else{
				z=0;zz=0;
			}
			upd(1,a,1);
		}
		if(mid<=a){
			l=mid;r=a;z=-1;zz=P[t].second;
			upd(1,a,1);
		}
	}
	
	
	//cout<<endl<<endl<<endl;
	for(i=1; i<=a; i++){
		l=i;z=-1;zz=0;
		read(1,a,1);
		//cout<<z<<" "<<zz<<endl;
		if(z==-1){
			zx=zz;
		}
		if(z==0){
			zx=zz;
		}
		if(z==1){
			zx=f[i]+zz;
		}
		//ANS.push_back(zx);
		ans[Q[i].second]=zx;
	}
	for(i=1; i<=a; i++){
		ANS.push_back(ans[i]);
	}
	return ANS;
}

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