Submission #1126266

#TimeUsernameProblemLanguageResultExecution timeMemory
1126266Tyx2019Distributing Candies (IOI21_candies)C++20
Compilation error
0 ms0 KiB
#include "candies_ioi.h" #include <bits/stdc++.h> #define int long long #define debug(x) if(0) cout << #x << " is " << x << endl; using namespace std; vector<int> C, L, R, V; const int INF = 1e18; int N, Q; struct mxsubarr{ int maxsum, sum, maxpref, maxsuf; int32_t endidx, prefendidx; mxsubarr(int a, int b, int c, int d, int e, int f){ maxsum = a; sum = b; maxpref = c; maxsuf = d; endidx = e; prefendidx = f; } }; mxsubarr* merge(mxsubarr* l, mxsubarr* r){ int sum, maxpref, maxsuf, maxsum; int32_t endidx, prefendidx; sum = l->sum + r->sum; maxpref = max(l->maxpref, l->sum + r->maxpref); if(l->maxpref == maxpref) prefendidx = l->prefendidx; else prefendidx = r->prefendidx; maxsuf = max(r->maxsuf, r->sum + l->maxsuf); maxsum = max({l->maxsum, r->maxsum, l->maxsuf + r->maxpref}); if(l->maxsum == maxsum) endidx = l->endidx; else if(r->maxsum == maxsum) endidx = r->endidx; else endidx = r->prefendidx; mxsubarr* ret = new mxsubarr(maxsum, sum, maxpref, maxsuf, endidx, prefendidx); return ret; } struct kadane{ int S, E, M; int maxsum, sum, maxpref, maxsuf; int32_t endidx, prefendidx; kadane *l, *r; kadane(int _S, int _E){ S = _S; E = _E; M = (S + E) >> 1; l = r = NULL; maxsum = sum = maxpref = maxsuf = 0; endidx = prefendidx = S; } void upd(int idx, int val){ if(!l) l = new kadane(S, M); if(!r) r = new kadane(M + 1, E); if(S == E){ maxsum = sum = maxpref = maxsuf = val; endidx = prefendidx = S; return; } if(idx <= M) l->upd(idx, val); else r->upd(idx, val); sum = l->sum + r->sum; maxpref = max(l->maxpref, l->sum + r->maxpref); if(l->maxpref == maxpref) prefendidx = l->prefendidx; else prefendidx = r->prefendidx; maxsuf = max(r->maxsuf, r->sum + l->maxsuf); maxsum = max({l->maxsum, r->maxsum, l->maxsuf + r->maxpref}); if(l->maxsum == maxsum) endidx = l->endidx; else if(r->maxsum == maxsum) endidx = r->endidx; else endidx = r->prefendidx; } mxsubarr* query(int start, int end){ if(!l) l = new kadane(S, M); if(!r) r = new kadane(M + 1, E); if(start == S && end == E) return new mxsubarr({maxsum, sum, maxpref, maxsuf, endidx, prefendidx}); else if(end <= M){ return l->query(start, end); } else if(start > M){ return r->query(start, end); } else{ return merge(l->query(start, M), r->query(M + 1, end)); } } }*seggs1, *seggs2; struct node{ //range add, range max, range min int S, E, M, mn, mx, ladd; node *l, *r; node(int _S, int _E){ S = _S; E = _E; M = (S + E) >> 1; mn = mx = ladd = 0; if(S == E) return; l = new node(S, M); r = new node(M + 1, E); } void prop(){ if(S == E) return; if(ladd != 0){ l->mn += ladd; l->mx += ladd; r->mn += ladd; r->mx += ladd; l->ladd += ladd; r->ladd += ladd; ladd = 0; } } void upd(int start, int end, int val){ prop(); debug(S) debug(E) debug(start) debug(end) debug(val) if(start == S && end == E){ ladd += val; mn += val; mx += val; return; } if(end <= M) l->upd(start, end, val); else if(start > M) r->upd(start, end, val); else{ l->upd(start, M, val); r->upd(M + 1, end, val); } mn = min(l->mn, r->mn); mx = max(l->mx, r->mx); } int range_min(int start, int end){ prop(); if(start == S && end == E) return mn; if(end <= M) return l->range_min(start, end); else if(start > M) return r->range_min(start, end); else return min(l->range_min(start, M), r->range_min(M + 1, end)); } int range_max(int start, int end){ prop(); if(start == S && end == E) return mx; if(end <= M) return l->range_max(start, end); else if(start > M) return r->range_max(start, end); else return max(l->range_max(start, M), r->range_max(M + 1, end)); } }*seggs3; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) { for(auto i:c) C.push_back(i); for(auto i:l) L.push_back(i); for(auto i:r) R.push_back(i); for(auto i:v) V.push_back(i); N = C.size(); Q = L.size(); debug(Q) debug(N) vector<int32_t> res(N, 0); seggs1 = new kadane(0, Q + 5); //normal seggs2 = new kadane(0, Q + 5); //negated seggs3 = new node(0, Q + 5); //prefixsum vector<int> add[N + 5]; vector<int> remove[N + 5]; for(int i=0;i<Q;i++){ add[L[i]].push_back(i); remove[R[i]+1].push_back(i); } for(int i=0;i<N;i++){ debug(i) debug(add[i].size()) for(auto j:add[i]){ debug("add") debug(j) seggs1->upd(j+1, V[j]); seggs2->upd(j+1, -V[j]); seggs3->upd(j+1, Q, V[j]); } for(auto j:remove[i]){ debug("remove") debug(j) seggs1->upd(j+1, 0); seggs2->upd(j+1, 0); seggs3->upd(j+1, Q, -V[j]); } debug("stuff") int lastmax = -1; int lastmin = 0; int lb = 1; int ub = Q; while(ub > lb){ debug(ub) debug(lb) int mid = (ub + lb + 1) >> 1; debug(seggs1->query(mid, Q)->maxsum) if(seggs1->query(mid, Q)->maxsum >= C[i]) lb = mid; else ub = mid - 1; } debug(seggs1->query(lb, Q)->maxsum) if(seggs1->query(lb, Q)->maxsum >= C[i]) lastmax = seggs1->query(lb, Q)->endidx; lb = 1; ub = Q; while(ub > lb){ debug(ub) debug(lb) int mid = (ub + lb + 1) >> 1; if(seggs2->query(mid, Q)->maxsum >= C[i]) lb = mid; else ub = mid - 1; } debug(lb) if(seggs2->query(lb, Q)->maxsum >= C[i]) lastmin = seggs2->query(lb, Q)->endidx; debug(lastmax) debug(lastmin) if(lastmax > lastmin){ int k = C[i] + seggs3->range_max(Q, Q) - seggs3->range_max(lastmax, Q); debug(k) debug(i) debug(seggs3->range_max(Q, Q)) debug(seggs3->range_max(lastmax, Q)) res[i] = k; } else{ int k = seggs3->range_max(Q, Q) - seggs3->range_min(lastmin, Q); debug(k) debug(i) debug(seggs3->range_max(Q, Q)) debug(seggs3->range_min(lastmin, Q)) res[i] = k; } } return res; }

Compilation message (stderr)

candies.cpp:1:10: fatal error: candies_ioi.h: No such file or directory
    1 | #include "candies_ioi.h"
      |          ^~~~~~~~~~~~~~~
compilation terminated.