Submission #1038921

#TimeUsernameProblemLanguageResultExecution timeMemory
1038921AndreyDistributing Candies (IOI21_candies)C++17
100 / 100
911 ms68436 KiB
#include "candies.h" #include<bits/stdc++.h> #include <vector> using namespace std; long long n,q; vector<pair<long long,long long>> haha[200001]; vector<pair<long long,long long>> big(1000001); vector<pair<long long,long long>> sm(1000001); vector<long long> wow(1000001); void build(long long l, long long r, long long x) { if(l == r) { big[x] = {0,l}; sm[x] = {0,-l}; return; } long long mid = (l+r)/2; build(l,mid,x*2); build(mid+1,r,x*2+1); big[x] = max(big[x*2],big[x*2+1]); sm[x] = min(sm[x*2],sm[x*2+1]); } void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) { if(l == ql && r == qr) { wow[x]+=br; big[x] = {big[x].first+br,big[x].second}; sm[x] = {sm[x].first+br,sm[x].second}; return; } long long mid = (l+r)/2; if(qr <= mid) { upd(l,mid,ql,qr,x*2,br); } else if(ql > mid) { upd(mid+1,r,ql,qr,x*2+1,br); } else { upd(l,mid,ql,mid,x*2,br); upd(mid+1,r,mid+1,qr,x*2+1,br); } big[x] = max(big[x*2],big[x*2+1]); sm[x] = min(sm[x*2],sm[x*2+1]); big[x] = {big[x].first+wow[x],big[x].second}; sm[x] = {sm[x].first+wow[x],sm[x].second}; } pair<long long,long long> calc(long long l, long long r, long long ql, long long qr, long long x, bool y) { if(ql > qr) { return {0,-1}; } if(l == ql && r == qr) { if(y) { return big[x]; } else { return sm[x]; } } long long mid = (l+r)/2; pair<long long,long long> ans; if(qr <= mid) { ans = calc(l,mid,ql,qr,x*2,y); } else if(ql > mid) { ans = calc(mid+1,r,ql,qr,x*2+1,y); } else { pair<long long,long long> a = calc(l,mid,ql,mid,x*2,y); pair<long long,long long> b = calc(mid+1,r,mid+1,qr,x*2+1,y); if(y) { ans = max(a,b); } else { ans = min(a,b); } } ans = {ans.first+wow[x],ans.second}; return ans; } vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { n = c.size(); q = l.size(); for(long long i = 0; i < q; i++) { haha[l[i]].push_back({v[i],q+1-i}); haha[r[i]+1].push_back({-v[i],q+1-i}); } q++; build(1,q,1); vector<int> ans(n); for(long long i = 0; i < n; i++) { for(pair<long long,long long> v: haha[i]) { upd(1,q,v.second,q,1,v.first); } long long bl = 0,br = q; while(bl < br) { long long mid = (br+bl+1)/2; if(calc(1,q,1,mid,1,1).first-calc(1,q,1,mid,1,0).first < c[i]) { bl = mid; } else { br = mid-1; } } long long p = bl; if(p == q) { ans[i] = calc(1,q,1,q,1,1).first; } else { p++; pair<long long,long long> a = calc(1,q,1,p,1,1); pair<long long,long long> b = calc(1,q,1,p,1,0); b = {b.first,-b.second}; if(b.second > a.second) { ans[i] = a.first; } else { ans[i] = c[i]+b.first; } } } 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...