oj.uz

Submission #466840

# Submission time Handle Problem Language Result Execution time Memory
466840 2021-08-20T20:32:27 Z mosiashvililuka Distributing Candies (IOI21_candies) C++17
27 / 100
 1102 ms 15420 KB 
#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,C[200009],f[200009],tes,t,L[200009],R[200009],V[200009],T=300;
int lf[200009],rg[200009],le[200009],ri[200009];
int fun(int q){
	return (q-1)/T+1;
}
void reDO(int q){
	//cout<<"Test:"<<t<<"  "<<q<<endl;
	int mi=C[1]+3,qw=0,we=0;
	for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
		mi=min(mi,f[h]);
	}
	for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
		qw=f[h]-mi;
		if(qw<=le[q]){
			f[h]=lf[q];
		}else{
			qw-=le[q];
			f[h]=min(lf[q]+qw,rg[q]);
		}
	}
	for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
		if(h<L[t]||h>R[t]) continue;
		f[h]+=V[t];
		if(f[h]<0) f[h]=0;if(f[h]>C[1]) f[h]=C[1];
	}
	le[q]=0;ri[q]=0;lf[q]=C[1]+3;rg[q]=0;
	for(int h=(q-1)*T+1; h<=min(q*T,a); h++){
		lf[q]=min(lf[q],f[h]);rg[q]=max(rg[q],f[h]);
	}
}
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++) C[i]=Cc[i-1];
    for(t=1; t<=tes; t++){
    	L[t]=Ll[t-1]+1;R[t]=Rr[t-1]+1;V[t]=Vv[t-1];
	}
	
	for(t=1; t<=tes; t++){
		i=fun(L[t])+1;i=(i-1)*T+1;
		for( ; i<=a; i+=T){
			if(fun(i)>=fun(R[t])) break;
			ii=fun(i);
			if(V[t]>0){
				if(rg[ii]+V[t]<=C[1]){
					lf[ii]+=V[t];rg[ii]+=V[t];
				}else{
					ri[ii]+=min(rg[ii]-lf[ii],V[t]-(C[1]-rg[ii]));
					lf[ii]=min(lf[ii]+V[t],C[1]);rg[ii]=C[1];
				}
			}else{
				if(lf[ii]+V[t]>=0){
					lf[ii]+=V[t];rg[ii]+=V[t];
				}else{
					le[ii]+=min(rg[ii]-lf[ii],-V[t]-lf[ii]);
					lf[ii]=0;rg[ii]=max(rg[ii]+V[t],0);
				}
			}
		}
		ii=fun(L[t]);
		reDO(ii);
		if(ii!=fun(R[t])){
			ii=fun(R[t]);
			reDO(ii);
		}
	}
	for(ii=1; ; ii++){
		if((ii-1)*T+1>a) break;
		reDO(ii);
	}
	vector <int> ANS;
	for(i=1; i<=a; i++){
		ANS.push_back(f[i]);
	}
	return ANS;
}

Compilation message

candies.cpp: In function 'void reDO(int)':
candies.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |   if(f[h]<0) f[h]=0;if(f[h]>C[1]) f[h]=C[1];
      |   ^~
candies.cpp:27:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |   if(f[h]<0) f[h]=0;if(f[h]>C[1]) f[h]=C[1];
      |                     ^~
candies.cpp:11:21: warning: unused variable 'we' [-Wunused-variable]
   11 |  int mi=C[1]+3,qw=0,we=0;
      |                     ^~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 622 ms 7408 KB Output is correct
3 Correct 72 ms 5568 KB Output is correct
4 Correct 1102 ms 11652 KB Output is correct
5 Correct 1067 ms 15368 KB Output is correct
6 Correct 1036 ms 15368 KB Output is correct
7 Correct 1044 ms 15420 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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