Submission #1048146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048146		Edu175	Distributing Candies (IOI21_candies)	C++17	0 / 100	871 ms	47688 KiB

candies

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fjhg:v)cout<<fjhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

struct node{
	ll pre,suf,res,sum;
	node(ll v){pre=suf=sum=res=v;}
};
node NEUT(0);
node oper(node a, node b){
	auto c=a;
	c.res=max({a.res,b.res,a.suf+b.pre});
	c.pre=max(a.pre,a.sum+b.pre);
	c.suf=max(b.suf,a.suf+b.sum);
	c.sum=a.sum+b.sum;
	return c;
}
struct STree{
	vector<node>t; ll n;
	STree(ll n):t(2*n+5,NEUT),n(n){}
	void upd(ll p, node v){
		for(p+=n,t[p]=v;p>1;p>>=1)p^=p&1,t[p>>1]=oper(t[p],t[p^1]);
	}
	node query(ll l, ll r){
		node izq=NEUT,der=NEUT;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1){
			if(l&1)izq=oper(izq,t[l++]);
			if(r&1)der=oper(t[--r],der);
		}
		return oper(izq,der);
	}
};

vector<STree> st(2,STree(0));
ll n;
ll ci;
pair<bool,bool> can(ll p){
	auto res0=st[0].query(p,n).res;
	auto res1=st[1].query(p,n).res;
	// cout<<"can "<<p<<": "<<res0<<" "<<res1<<"\n";;
	return {res0>ci,res1>ci};
}
void upd(ll p, ll v){
	st[0].upd(p,v);
	st[1].upd(p,-v);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v){
	n=SZ(c); ll q=SZ(l);
	st[0]=st[1]=STree(n);
	vector<vector<ii>>upds(n+1);
	fore(i,0,q){
		r[i]++;
		upds[l[i]].pb({i,v[i]});
		upds[r[i]].pb({i,0});	
	}
	vector<int>res(n);
	fore(i,0,n){
		for(auto [p,v]:upds[i])upd(p,v);
		ci=c[i];
		ll l=0,r=n-1;
		while(l<=r){
			ll m=(l+r)/2;
			auto rq=can(m);
			if(rq.fst||rq.snd)l=m+1;
			else r=m-1;
		}
		if(r>=0){
			auto rq=can(r);
			if(rq.fst)res[i]=c[i];
			else res[i]=0;
			// cout<<r<<" r "<<rq.fst<<","<<rq.snd<<"\n";
		}
		// cout<<i<<": "<<l<<" "<<res[i]<<"\n";
		
		// fore(h,0,2){
		// fore(i,0,n)cout<<st[h].query(i,i+1).sum<<" ";;cout<<"\n";
		// }
		// cout<<"\n";
		res[i]+=st[0].query(l,n).sum;
	}
	return res;
}
									

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