| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1126266 | Tyx2019 | 사탕 분배 (IOI21_candies) | C++20 | 0 ms | 0 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;
}