oj.uz

Submission #491256

# Submission time Handle Problem Language Result Execution time Memory
491256 2021-12-01T07:39:54 Z mosiashvililuka Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 21792 KB 
#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
const long long N=1000000000000000000LL;
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;
pair <long long, long long> p[200009];
vector <int> ans;
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);
	e=1;
	for(i=1; i<=a; i++){
		while(e<=pi&&p[e].first<=i){
			ii=p[e].second;
			if(ii>0){
				f[ii]=V[ii];
			}else{
				f[-ii]=0;
			}
			e++;
		}
		for(j=1; j<=tes; j++){
			F[j]=F[j-1]+f[j];
		}
		mn=N;mx=-N;
		for(j=tes; j>=1; j--){
			mn=min(mn,F[j]);mx=max(mx,F[j]);
			if(mx-mn>=C[i]){
				/*zx=F[tes]-F[j+1];
				if(F[j]==mn) ans[i-1]=C[i]+zx; else ans[i-1]=zx;*/
				if(F[j]==mn){
					ans[i-1]=C[i]+(F[tes]-mx);
				}else{
					ans[i-1]=F[tes]-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 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 14 ms 616 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 21792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1166 ms 18628 KB Output isn't correct
4 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 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 14 ms 616 KB Output is correct
6 Execution timed out 5077 ms 21792 KB Time limit exceeded
7 Halted 0 ms 0 KB -