Submission #939597

#TimeUsernameProblemLanguageResultExecution timeMemory
939597IS_RushdiDistributing Candies (IOI21_candies)C++17
0 / 100
613 ms31688 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; typedef int64_t i64; #define VII vector<int> struct seg{ vector<i64>mx,mn,cmx,cmn,op; int sz = 1; void build(int x,int lx,int rx){ if(rx-lx == 1){ cmx[x] = cmn[x] = 1; return; } int m = (lx+rx)/2; build(x*2+1,lx,m); build(x*2+2,m,rx); cmx[x] = cmx[x*2+1] + cmx[x*2+2]; cmn[x] = cmn[x*2+1] + cmn[x*2+2]; } seg(int n){ while(sz < n) sz*=2; op.assign(sz*2,0ll); mx.assign(sz*2,0ll); mn.assign(sz*2,0ll); cmx.assign(sz*2,0ll); cmn.assign(sz*2,0ll); build(0,0,sz); } void push(int x,int lx,int rx){ if(rx-lx == 1) return; op[x*2+1] += op[x]; op[x*2+2] += op[x]; int m = (lx+rx)/2; NQF(x*2+1,lx,m); NQF(x*2+2,m,rx); op[x] = 0; } void NQF(int x,int lx,int rx){ if(rx-lx == 1){ cmx[x] = cmn[x] = 1; mn[x] = mx[x] = op[x]; return; } mx[x] = max(mx[x*2+1],mx[x*2+2]) + op[x]; mn[x] = min(mn[x*2+1],mn[x*2+2]) + op[x]; if(mx[x*2+1] > mx[x*2+2]) cmx[x] = cmx[x*2+1]; else if(mx[x*2+2] > mx[x*2+1]) cmx[x] = cmx[x*2+2]; else cmx[x] = cmx[x*2+1] + cmx[x*2+2]; if(mn[x*2+1] < mn[x*2+2]) cmn[x] = cmn[x*2+1]; else if(mn[x*2+2] < mn[x*2+1]) cmn[x] = cmn[x*2+2]; else cmn[x] = cmn[x*2+1] + cmn[x*2+2]; } void update(int l,int r,int v,int x=0,int lx=0,int rx=-1){ if(rx == -1) rx = sz; if(rx <= l || lx >= r) return; push(x,lx,rx); if(rx <= r && lx >= l){ mn[x] += v; mx[x] += v; op[x] += v; return; } int m = (lx+rx)/2; update(l,r,v,x*2+1,lx,m); update(l,r,v,x*2+2,m,rx); NQF(x,lx,rx); push(x,lx,rx); } void checkMAX(int v,int x=0,int lx=0,int rx=-1){ if(rx == -1) rx = sz; NQF(x,lx,rx); push(x,lx,rx); if(mx[x] > v){ if(cmx[x] == (rx-lx)){ op[x] -= mx[x]-v; }else{ int m = (lx+rx)/2; checkMAX(v,x*2+1,lx,m); checkMAX(v,x*2+2,m,rx); } } NQF(x,lx,rx); push(x,lx,rx); } void checkMIN(int x=0,int lx=0,int rx=-1){ if(rx == -1) rx = sz; NQF(x,lx,rx); push(x,lx,rx); if(mn[x] < 0){ if(cmx[x] == rx-lx){ op[x] -= mn[x]; push(x,lx,rx); }else{ int m = (lx+rx)/2; checkMIN(x*2+1,lx,m); checkMIN(x*2+2,m,rx); } } NQF(x,lx,rx); push(x,lx,rx); } int get(int i,int x=0,int lx=0,int rx=-1){ if(rx == -1) rx = sz; if(rx-lx == 1) return op[x]; int m = (lx+rx)/2; if(i < m) return op[x] + get(i,x*2+1,lx,m); else return op[x] + get(i,x*2+2,m,rx); } }; VII distribute_candies(VII c,VII l ,VII r,VII v) { int n = c.size(); int q = l.size(); seg st(n+1); for(int i = 0; i < q; i++){ st.update(l[i],r[i]+1,v[i]); if(v[i] > 0 && i == 1){ st.checkMAX(c[0]); }else{ st.checkMIN(); } } vector<int>ans; for(int i = 0; i < n; i++) ans.push_back(st.get(i)); return ans; } // int main(){ // int n,q; cin >> n >> q; // vector<int>l(q),r(q),v(q),c(n); // for(int i = 0; i < n; i++) cin >> c[i]; // for(int i = 0; i < q; i++){ // cin >> l[i] >> r[i] >> v[i]; // } // vector<int>ans = distribute_candies(c,l,r,v); // for(int x : ans){ // cout << x << ' '; // } // }
#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...