| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 721386 | urosk | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#define here cerr<<"======================================\n"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define llinf 1000000000000000000LL
#define dbg(x) cerr<<#x<<": "<<x<<endl
using namespace std;
#define maxn 200005
ll n,q;
ll c[maxn];
vector<pll> v[maxn];
ll lazy[2*maxn];
ll ls[2*maxn],rs[2*maxn],root,tsz = 0;
struct nod{
ll mx,mn,mxid,mnid,val;
} t[2*maxn];
nod def,def0;
nod f(nod l,nod r){
nod ans;
ans.mn = min(l.mn,r.mn);
ans.mx = max(l.mx,r.mx);
if(l.mn<r.mn) ans.mnid = l.mnid;
else ans.mnid = r.mnid;
if(l.mx>r.mx) ans.mxid = l.mxid;
else ans.mxid = r.mxid;
ans.val = ans.mx-ans.mn;
return ans;
}
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
t[v].mn = 0;
t[v].mx = 0;
t[v].mxid = tr;
t[v].mnid = tr;
t[v].val = 0;
if(tl==tr) return;
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
void push(ll v,ll tl,ll tr){
if(lazy[v]==0) return;
t[v].mn+=lazy[v];
t[v].mx+=lazy[v];
if(tl<tr){
lazy[ls[v]]+=lazy[v];
lazy[rs[v]]+=lazy[v];
}
lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
push(v,tl,tr);
if(l>r||tl>tr||l>tr||tl>r) return;
if(tl>=l&&tr<=r){
lazy[v]+=x;
push(v,tl,tr);
return;
}
ll mid = (tl+tr)/2;
upd(ls[v],tl,mid,l,r,x);
upd(rs[v],mid+1,tr,l,r,x);
t[v] = f(t[ls[v]],t[rs[v]]);
}
ll get(ll v,ll tl,ll tr,ll x,nod cur){
push(v,tl,tr);
nod cur2 = f(t[v],cur);
if(cur2.val<x) return -1;
if(tl==tr) return tl;
ll mid = (tl+tr)/2;
push(ls[v],tl,tr);
push(rs[v],mid+1,tr);
ll ans = get(rs[v],mid+1,tr,x,cur);
if(ans==-1) return get(ls[v],tl,mid,x,f(t[rs[v]],cur));
return ans;
}
nod get(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r||l>tr||tl>tr||tl>r) return def0;
if(tl>=l&&tr<=r) return t[v];
ll mid = (tl+tr)/2;
return f(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
}
vector<int> ans;
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> VAL) {
n = C.size();
q = L.size();
for(ll i = 1;i<=n;i++) c[i] = C[i-1];
for(ll i = 1;i<=q;i++){
v[L[i-1]+1].pb({VAL[i-1],i+2});
v[R[i-1]+2].pb({-VAL[i-1],i+2});
}
q+=2;
init(root,1,q);
ll sum = 0;
nod def0;
def0.mn = llinf;
def0.mx = -llinf;
def0.mnid = def0.mxid = q+1;
def0.val = 0;
for(ll i = 1;i<=n;i++){
for(pll p : v[i]){
ll x = p.fi;
ll i = p.sc;
upd(root,1,q,i,q,x);
sum+=x;
}
push(1,1,q);
if(t[1].val<=c[i]){
if(t[1].mx>c[i]) ans.pb(c[i]+(sum-t[1].mx));
else{
ll j = t[1].mnid;
if(t[1].mn<0) ans.pb(sum-t[1].mn);
else ans.pb(sum);
}
continue;
}
nod def;
def.mn = llinf;
def.mx = -llinf;
def.mxid = q+1;
def.mnid = q+1;
def.val = 0;
ll j = get(1,1,q,c[i],def);
nod cur = get(1,1,q,j,q);
ll minid = cur.mnid;
ll maxid = cur.mxid;
if(minid>maxid) ans.pb(min(c[i],sum-cur.mn));
else ans.pb(max(0LL,c[i]+(sum-cur.mx)));
}
for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],ans[i]));
return ans;
}
/**
3
10 15 13
2
0 2 20
0 1 -11
3
10 15 13
2
0 1 13
0 2 7
**/