Submission #1303629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303629		vtnoo	Distributing Candies (IOI21_candies)	C++20	0 / 100	69 ms	9828 KiB

candies

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
struct Nodo{
	int mn=0,mx=0,lz=0;
};
Nodo st[MAXN*4];
int n,lim;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=SZ(c);
    int q=SZ(l);
	vector<int>p(q+1,0),sufMax(q+1,0),sufMin(q+1,0);
	fore(i,0,q){
		p[i+1]=v[i];
		if(i)p[i+1]+=p[i];
	}
	sufMax[q]=sufMin[q]=p[q];
	for(int i=q-1;i>=0;i--){
		sufMax[i]=sufMin[i]=p[i];
		sufMax[i]=max(sufMax[i],sufMax[i+1]);
		sufMin[i]=min(sufMin[i],sufMin[i+1]);
	}
	//~ fore(i,0,q+1)cout<<sufMax[i]<<" ";
	//~ cout<<endl;
	//~ fore(i,0,q+1)cout<<sufMin[i]<<" ";
	//~ cout<<endl;
	//~ fore(i,0,q+1)cout<<p[i]<<" ";
	//~ cout<<endl;
	vector<int>ret(n);
	fore(i,0,n){
		int L=0,R=q+1;
		if(sufMax[0]-sufMin[0]<c[i]){
			ret[i]=p[q]-sufMin[0];
			continue;
		}
		while(R-L>1){
			int m=(L+R)/2;
			if(sufMax[m]-sufMin[m]>=c[i]){
				L=m;
			}else R=m;
		}
		if(sufMin[L]==p[L]){
			ret[i]=c[i]-(sufMax[L]-p[q]);
		}else{
			ret[i]=p[q]-sufMin[L];
		}
	}
	return ret;
}

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