제출 #1126279

#제출 시각아이디문제언어결과실행 시간메모리
1126279Tyx2019사탕 분배 (IOI21_candies)C++20
컴파일 에러
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; #pragma GCC optimise("Ofast"); 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; mxsubarr* vals; kadane *l, *r; kadane(int _S, int _E){ S = _S; E = _E; M = (S + E) >> 1; l = r = NULL; vals = new mxsubarr(0, 0, 0, 0, S, 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){ vals = new mxsubarr(val, val, val, val, S, S); return; } if(idx <= M) l->upd(idx, val); else r->upd(idx, val); vals = merge(l->vals, r->vals); } int bsta(int goal, mxsubarr* right){ if(S == E){ auto k = merge(vals, right); return k->endidx; } auto k = merge(r->vals, right); if(k->maxsum >= goal){ return r->bsta(goal, right); } else{ return l->bsta(goal, k); } } }*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(); 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; vector<int32_t> distribute_candies(vector<int32_t> C, vector<int32_t> L, vector<int32_t> R, vector<int32_t> V) { 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++){ for(auto j:add[i]){ seggs1->upd(j+1, V[j]); seggs2->upd(j+1, -V[j]); seggs3->upd(j+1, Q, V[j]); } for(auto j:remove[i]){ seggs1->upd(j+1, 0); seggs2->upd(j+1, 0); seggs3->upd(j+1, Q, -V[j]); } int lastmax = -1; int lastmin = 0; auto k = new mxsubarr(-1000, -1000, -1000, -1000, 69, 69); if(seggs1->vals->maxsum >= C[i]) lastmax = seggs1->bsta(C[i], k); if(seggs2->vals->maxsum >= C[i]) lastmin = seggs2->bsta(C[i], k); if(lastmax > lastmin){ int k = C[i] + seggs3->range_max(Q, Q) - seggs3->range_max(lastmax, Q); res[i] = k; } else{ int k = seggs3->range_max(Q, Q) - seggs3->range_min(lastmin, Q); res[i] = k; } } return res; }

컴파일 시 표준 에러 (stderr) 메시지

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