oj.uz

Submission #435754

# Submission time Handle Problem Language Result Execution time Memory
435754 2021-06-23T16:50:54 Z mosiashvililuka Distributing Candies (IOI21_candies) C++17
29 / 100
 831 ms 19956 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Incorrect 4 ms 6460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 591 ms 19904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6604 KB Output is correct
3 Correct 296 ms 13668 KB Output is correct
4 Correct 118 ms 13080 KB Output is correct
5 Correct 773 ms 19952 KB Output is correct
6 Correct 828 ms 19956 KB Output is correct
7 Correct 831 ms 19952 KB Output is correct
8 Correct 804 ms 19948 KB Output is correct
9 Correct 514 ms 19952 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Incorrect 4 ms 6460 KB Output isn't correct
3 Halted 0 ms 0 KB -