oj.uz

Submission #491266

# Submission time Handle Problem Language Result Execution time Memory
491266 2021-12-01T09:05:12 Z mosiashvililuka Distributing Candies (IOI21_candies) C++17
32 / 100
 973 ms 57152 KB 
#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
const long long N=1000000000000000000LL,S=800003,T=800004;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,C[200009],L[200009],R[200009],V[200009],f[200009],pi,F[200009],mn,mx,l,r,z,za,seg[800009],segmn[800009],segmx[800009],lef,rig,mid;
pair <long long, long long> p[200009];
vector <int> ans;
void upd(int rr){
	if(rr==0) return;
	seg[rr]=seg[rr*2]+seg[rr*2+1];
	segmn[rr]=min(segmn[rr*2],seg[rr*2]+segmn[rr*2+1]);
	segmx[rr]=max(segmx[rr*2],seg[rr*2]+segmx[rr*2+1]);
	upd(rr/2);
}
void UPD(int q){
	seg[q+za-1]=f[q];
	/*segmn[q+za-1]=min(0LL,f[q]);
	segmx[q+za-1]=max(0LL,f[q]);*/
	segmn[q+za-1]=f[q];
	segmx[q+za-1]=f[q];
	upd((q+za-1)/2);
}
void read(int q, int w, int rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		seg[T]=seg[S]+seg[rr];
		segmn[T]=min(segmn[S],seg[S]+segmn[rr]);
		segmx[T]=max(segmx[S],seg[S]+segmx[rr]);
		swap(seg[S],seg[T]);swap(segmn[S],segmn[T]);swap(segmx[S],segmx[T]);
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((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();ans.resize(a);
    for(i=1; i<=a; i++){
    	C[i]=Cc[i-1];
	}
	L[1]=1;R[1]=a;V[1]=N;
	L[2]=1;R[2]=a;V[2]=-N;tes+=2;
	for(t=3; t<=tes; t++){
		L[t]=Ll[t-3]+1;R[t]=Rr[t-3]+1;V[t]=Vv[t-3];
	}
	for(t=1; t<=tes; t++){
		pi++;p[pi]={L[t],t};pi++;p[pi]={R[t]+1,-t};
	}
	sort(p+1,p+pi+1);
	za=1;
	while(za<tes) za*=2;
	int ee=1;
	for(i=1; i<=a; i++){
		while(ee<=pi&&p[ee].first<=i){
			ii=p[ee].second;
			if(ii>0){
				f[ii]=V[ii];
				UPD(ii);
			}else{
				//cout<<ii<<" UPD\n";
				f[-ii]=0;
				UPD(-ii);
			}
			ee++;
		}
		//cout<<i<<" seg "<<seg[1]<<"\n";
		/*for(j=1; j<=tes; j++){
			F[j]=F[j-1]+f[j];
		}*/
		mn=N;mx=-N;
		//for(j=tes; j>=1; j--){
			lef=0;rig=tes+1;
			while(1){
				if(lef+1>=rig) break;
				mid=(lef+rig)/2;
				l=mid;r=tes;seg[S]=0;segmn[S]=N;segmx[S]=-N;
				read(1,za,1);mn=segmn[S];mx=segmx[S];
				if(mx-mn>=C[i]){
					lef=mid;
				}else{
					rig=mid;
				}
				//cout<<mid<<" mid "<<mn<<" "<<mx<<"\n";
			}
			//return ans;
			mid=lef;
			l=mid;r=tes;seg[S]=0;segmn[S]=N;segmx[S]=-N;
			read(1,za,1);mn=segmn[S];mx=segmx[S];
			//
			zx=seg[1];
			l=1;r=mid;seg[S]=0;segmn[S]=N;segmx[S]=-N;
			read(1,za,1);xc=seg[S];
			e=xc-f[mid];
			mn+=e;mx+=e;
			//
			/*cout<<mid<<" MID\n";
			cout<<i<<": "<<mn<<" "<<mx<<"\n";
			cout<<zx<<" zx "<<xc<<"\n";*/
			//mn=min(mn,F[j]);mx=max(mx,F[j]);
			if(mx-mn>=C[i]){
				/*if(F[j]==mn){
					ans[i-1]=C[i]+(F[tes]-mx);
				}else{
					ans[i-1]=F[tes]-mn;
				}*/
				if(xc==mn){
					ans[i-1]=C[i]+(zx-mx);
				}else{
					ans[i-1]=zx-mn;
				}
				//break;
			}
		//}
	}
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 7 ms 712 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 795 ms 57152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 162 ms 49260 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 107 ms 24412 KB Output is correct
4 Correct 328 ms 6628 KB Output is correct
5 Correct 849 ms 32232 KB Output is correct
6 Correct 805 ms 33200 KB Output is correct
7 Correct 736 ms 33732 KB Output is correct
8 Correct 889 ms 32416 KB Output is correct
9 Correct 973 ms 33956 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 7 ms 712 KB Output is correct
6 Runtime error 795 ms 57152 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -