Submission #1145492

#TimeUsernameProblemLanguageResultExecution timeMemory
1145492midiDistributing Candies (IOI21_candies)C++20
0 / 100
444 ms45668 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define vc vector typedef vc<ll> vcll; typedef vc<bool> vcb; #define pr pair typedef pr<ll, ll> prll; typedef set<ll> setll; typedef map<ll,ll> mapll; #define uset unordered_set typedef uset<ll> usetll; #define umap unordered_map typedef umap<ll,ll> umapll; #define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++) #define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--) #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define mp make_pair #define fi first #define se second #define sz size #define all(x) (x).begin(), (x).end() #define all0(x, n) (x).begin(), (x).begin()+n #define all1(x, n) (x).begin()+1, (x).begin()+n+1 #define allrev(x) (x).rbegin(), (x).rend() #define in(v, s) ((s).find((v)) != (s).end()) #define GCD(x, y) __gcd(abs((x)), abs((y))) #define INF (LLONG_MAX>>3ll) #define MOD (1'000'000'007ll) #define mxN (200'010ll) #define sgN (1ll<<18ll) #define mxQ (200'010ll) inline void maxa(ll &a, ll b) { if (a<b) a=b; } inline void mina(ll &a, ll b) { if (a>b) a=b; } inline void print (vcll &a, ll n=-1, string name="") { cout << name << ": "; if (n==-1) for (ll x:a) printf("%lli ", x); else { ll i; f0r(i,1,n) printf("%lli ", a[i]); } printf("\n"); } ll n, q; vcll C(mxN), L(mxQ), R(mxQ), X(mxQ); vc<vc<prll>> qs(mxN); struct ST { struct nd { ll mx, mn, s, lz; inline nd() { mx=mn=s=lz=0; } }; vc<nd> st; inline ST() { st.resize(sgN*2+10); } inline void prop (ll it, ll lt, ll rt) { ll lz=st[it].lz; st[it].lz=0; st[it].mx+=lz; st[it].mn+=lz; st[it].s+=lz*(rt-lt); if (lt+1==rt) return; ll i2=it*2; st[i2].lz+=lz; st[i2+1].lz+=lz; } ll minp (ll it, ll lt, ll rt, ll l, ll r) { prop(it,lt,rt); if (rt<=l or r<=lt) return INF; if (l<=lt and rt<=r) return st[it].mn; ll i2=it*2, mt=(lt+rt)/2; return min( minp(i2,lt,mt,l,r), minp(i2+1,mt,rt,l,r)); } inline ll minp (ll l, ll r) { return minp(1,0,q+1,l,r+1); } ll maxp (ll it, ll lt, ll rt, ll l, ll r) { prop(it,lt,rt); if (rt<=l or r<=lt) return -INF; if (l<=lt and rt<=r) return st[it].mx; ll i2=it*2, mt=(lt+rt)/2; return max( maxp(i2,lt,mt,l,r), maxp(i2+1,mt,rt,l,r)); } inline ll maxp (ll l, ll r) { return maxp(1,0,q+1,l,r+1); } ll acc (ll it, ll lt, ll rt, ll j) // works with min { prop(it,lt,rt); if (rt<=j or j<lt) return INF; if (lt+1==rt) return st[it].mn; ll i2=it*2, mt=(lt+rt)/2; return min( acc (i2,lt,mt,j), acc(i2+1,mt,rt,j)); } inline ll acc (ll j) { return acc(1,0,q+1,j); } ll maxl (ll it, ll lt, ll rt, ll c, ll mx, ll mn) { prop(it,lt,rt); if (max(mx,st[it].mx)-min(mn,st[it].mn) < c) return -1; if (lt+1==rt) return lt; ll i2=it*2, mt=(lt+rt)/2; ll res=maxl(i2+1,mt,rt,c,mx,mn); if (res!=-1) return res; return maxl(i2,lt,mt,c, max(mx,st[it].mx), min(mn,st[it].mn)); } inline ll maxl (ll c) { return maxl (1,0,q+1,c,-INF,INF); } inline void merge (ll it, ll lt, ll rt) { ll i2=it*2; st[it].mx = max(st[i2].mx, st[i2+1].mx); st[it].mn = min(st[i2].mn, st[i2+1].mn); st[it].s = st[i2].s + st[i2+1].s; } void upd (ll it, ll lt, ll rt, ll l, ll r, ll x) { prop(it,lt,rt); if (rt<=l or r<=lt) return; if (l<=lt and rt<=r) { st[it].lz+=x; prop(it,lt,rt); return; } ll i2=it*2, mt=(lt+rt)/2; upd (i2,lt,mt,l,r,x); upd (i2+1,mt,rt,l,r,x); merge(it,lt,rt); } inline void upd (ll l, ll r, ll x) { upd (1,0,q+1,l,r+1,x); } } st; inline void upd (ll i, ll x) { st.upd(i,q,x); } inline bool case1 (ll l, ll c) { ll pr=st.maxp(l,q), pl=st.acc(l); return pr-pl>=c; } inline ll qry (ll c) { ll l=st.maxl(c); if (case1(l,c)) { ll pn=st.acc(q), pr=st.maxp(l,q); return c+pn-pr; } else { ll pn=st.acc(q), pr=st.minp(l,q); return pn-pr; } } inline void bd_qs() { ll i; f0r(i,1,q) { ll l=L[i], r=R[i], x=X[i]; qs[l].pb({i,x}); qs[r+1].pb({i,-x}); } } vc<int> distribute_candies(vc<int> C1, vc<int> L1, vc<int> R1, vc<int> X1) { n=C1.sz(); q=L1.sz(); ll i; f0r(i,1,n) C[i]=C1[i-1]; f0r(i,1,q) { L[i]=L1[i-1]+1; R[i]=R1[i-1]+1; X[i]=X1[i-1]; } bd_qs(); vc<int> ans; f0r(i,1,n) { for (prll jx:qs[i]) upd(jx.fi, jx.se); ans.pb(qry(C[i])); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...