Submission #711224

#TimeUsernameProblemLanguageResultExecution timeMemory
711224myrcellaDistributing Candies (IOI21_candies)C++17
11 / 100
1290 ms15392 KiB
//by szh #include<bits/stdc++.h> #include "candies.h" using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const int maxn = 200010; int n,m; int hi[maxn]; pii hii[maxn]; vector <int> ans; vector <ll> anss; struct Q{ int l,r,v; }q[maxn]; vector <int> solve1() { rep(i,0,n) ans.pb(0); rep(i,0,m) { rep(j,q[i].l,q[i].r+1) { ans[j] += q[i].v; if (ans[j]<0) ans[j]=0; if (ans[j]>hi[j]) ans[j] = hi[j]; } } return ans; } vector <int> solve2(){ rep(i,0,n) anss.pb(0); rep(i,0,m) { anss[q[i].l]+=q[i].v; if (q[i].r+1<SZ(anss))anss[q[i].r+1]-=q[i].v; } rep(i,1,n) anss[i] += anss[i-1]; rep(i,0,n) { if (anss[i]>hi[i]) ans.pb(hi[i]); else ans.pb(anss[i]); } return ans; } vector <int> solve3() { return ans; } pii tree[maxn*4]; pii add[maxn*4]; void init(int c,int cl,int cr) { if (cl==cr) { tree[c]={1,0}; add[c]={0,0}; } else { int mid=cl+cr>>1; init(c<<1,cl,mid); init(c<<1|1,mid+1,cr); } } void push_down(int c) { if (add[c].fi!=0) { tree[c<<1] = tree[c<<1|1] = add[c<<1] = add[c<<1|1] = add[c]; } else { tree[c<<1].se += add[c].se; tree[c<<1|1].se += add[c].se; add[c<<1].se += add[c].se; add[c<<1|1].se += add[c].se; } add[c] = {0,0}; } void update(int c,int cl,int cr,int l,int r,int type,int val) { if (l<=cl and cr<=r) { if (type==0) { tree[c].se += val; add[c].se += val; } else if (type==1) { tree[c] = {1,0}; add[c] = {1,0}; } else tree[c] = {2,0},add[c] = {2,0}; return; } push_down(c); int mid = cl+cr>>1; if (l<=mid) update(c<<1,cl,mid,l,r,type,val); if (r>mid) update(c<<1|1,mid+1,cr,l,r,type,val); return; } pii query(int c,int cl,int cr,int pos) { if (cl==cr) return tree[c]; push_down(c); int mid=cl+cr>>1; if (pos<=mid) return query(c<<1,cl,mid,pos); else return query(c<<1|1,mid+1,cr,pos); } int query(int pos) { pii tmp = query(1,0,n-1,pos); if (tmp.fi==1) return tmp.se; else return hii[pos].fi+tmp.se; } std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { n = SZ(c),m = SZ(l); rep(i,0,n) hi[i] = c[i],hii[i] = {c[i],i}; rep(i,0,m) q[i].l = l[i],q[i].r = r[i], q[i].v = v[i]; if (n<=2000) return solve1(); bool check=true; rep(i,1,n) if (c[i]!=c[i-1]) check=false; if (check) return solve3(); check=true; rep(i,0,m) if (v[i]<=0) check=false; if (check) return solve2(); //subtask 4 init(1,0,n-1); rep(i,0,n) ans.pb(0); sort(hii,hii+n); rep(i,0,m) { int cur = q[i].v; if (cur==0) continue; if (cur<0) { int l = -1,r=n-1; while (l<r) { int mid=l+r+1>>1; if (mid==-1 or query(mid)+cur<0) l=mid; else r = mid-1; } if (l>=0) update(1,0,n-1,0,l,1,0); if (l+1<n) update(1,0,n-1,l+1,n-1,0,cur); } else { int l = -1,r=n-1; while (l<r) { int mid=l+r+1>>1; if (mid==-1 or query(mid)+cur>hii[mid].fi) l=mid; else r = mid-1; } if (l>=0) update(1,0,n-1,0,l,1,0); if (l+1<n) update(1,0,n-1,l+1,n-1,0,cur); } // debug(query(0));debug(query(2)); } rep(i,0,n) ans[hii[i].se]=(query(i)); return ans; }

Compilation message (stderr)

candies.cpp: In function 'void init(int, int, int)':
candies.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid=cl+cr>>1;
      |           ~~^~~
candies.cpp: In function 'void update(int, int, int, int, int, int, int)':
candies.cpp:109:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |  int mid = cl+cr>>1;
      |            ~~^~~
candies.cpp: In function 'std::pair<int, int> query(int, int, int, int)':
candies.cpp:118:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |  int mid=cl+cr>>1;
      |          ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:152:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |     int mid=l+r+1>>1;
      |             ~~~^~
candies.cpp:162:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |     int mid=l+r+1>>1;
      |             ~~~^~
#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...