| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1246459 | Boomyday | 사탕 분배 (IOI21_candies) | C++20 | 0 ms | 0 KiB |
//
// Created by adavy on 7/23/2025.
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int ssz = 262144; // segment tree where the x axis is time
const ll INF = 1e18; // careful!
vector<ll> sg_min(2*ssz, 0), lz_min(2*ssz, 0), sg_max(2*ssz, 0), lz_max(2*ssz, 0);
void push_min(int rt, int tl, int tr){
sg_min[rt] += lz_min[rt];
if (tl != tr) {
lz_min[2*rt] += lz_min[rt];
lz_min[2*rt+1] += lz_min[rt];
}
lz_min[rt] = 0;
}
void push_max(int rt, int tl, int tr){
sg_max[rt] += lz_max[rt];
if (tl != tr) {
lz_max[2*rt] += lz_max[rt];
lz_max[2*rt+1] += lz_max[rt];
}
lz_max[rt] = 0;
}
void upd_min(ll x, int l, int r, int rt, int tl, int tr){
push_min(rt, tl, tr);
if (r < tl || l > tr) return;
if (l <= tl && tr <= r) {
lz_min[rt] += x;
push_min(rt, tl, tr);
return;
}
int mid = (tl + tr) / 2;
upd_min(x, l, r, 2*rt, tl, mid);
upd_min(x, l, r, 2*rt+1, mid+1, tr);
sg_min[rt] = min(sg_min[2*rt], sg_min[2*rt+1]);
}
void upd_max(ll x, int l, int r, int rt, int tl, int tr){
push_max(rt, tl, tr);
if (r < tl || l > tr) return;
if (l <= tl && tr <= r) {
lz_max[rt] += x;
push_max(rt, tl, tr);
return;
}
int mid = (tl + tr) / 2;
upd_max(x, l, r, 2*rt, tl, mid);
upd_max(x, l, r, 2*rt+1, mid+1, tr);
sg_max[rt] = max(sg_max[2*rt], sg_max[2*rt+1]);
}
ll query_min(int l, int r, int rt, int tl, int tr){
push_min(rt, tl, tr);
if (r < tl || l > tr) return INF;
if (l <= tl && tr <= r) return sg_min[rt];
int mid = (tl + tr) / 2;
return min(query_min(l, r, 2*rt, tl, mid), query_min(l, r, 2*rt+1, mid+1, tr));
}
ll query_max(int l, int r, int rt, int tl, int tr){
push_max(rt, tl, tr);
if (r < tl || l > tr) return -INF;
if (l <= tl && tr <= r) return sg_max[rt];
int mid = (tl + tr) / 2;
return max(query_max(l, r, 2*rt, tl, mid), query_max(l, r, 2*rt+1, mid+1, tr));
}
int walk_index(ll c, int rt, int tl, int tr, ll&mn, ll&mx){
push_min(rt, tl, tr);
push_max(rt, tl, tr);
if (tl == tr) {
// we have found the LAST BAD index
mn = min(sg_min[rt], mn);
mx = max(sg_max[rt], mx);
return tl;
}
// check if right half is good or bad
if (max(mx, sg_max[2*rt+1])-min(mn, sg_min[2*rt+1]) >= c){
// right half is bad, recurse it
return walk_index(c, 2*rt+1, (tl + tr) / 2 + 1, tr, mn, mx);
}
// it's good
mx = max(mx, sg_max[2*rt+1]);
mn = min(mn, sg_min[2*rt+1]);
return walk_index(c, 2*rt, tl, (tl + tr) / 2, mn, mx);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n, q;
// adders (time position, value)
n = c.size();
q = l.size();
vector<vector<pair<ll,ll>>> add(n), sub(n); // represents the boxes
for(int i=0;i<q;++i){
add[l[i]].push_back({i+2, v[i]});
sub[r[i]].push_back({i+2, v[i]});
}
add[0].push_back({0, INF/2}); // deal with bottom edge correctly
add[1].push_back({1, -INF/2});
vector<int> ans(n, 0);
for(int i=0;i<n;++i){
// process additions
for(auto&[tm,vl]:add[i]){
upd_max(vl, tm, ssz-1, 1, 0, ssz-1);
upd_min(vl, tm, ssz-1, 1, 0, ssz-1);
}
// process query
// we need to do a binary search while walking on the segment tree to decide the index where a bad range no longer happens (size less than c[i])
// find the index of the first non-bad range and the entry before it, determine if that thing is the max or min
// for the walk, take a range [a, b], and find the values of [m,b]. If it's good, store the min and max values and do on the left subtree,
// if bad then just recurse this subtree.
ll mn = INF, mx = -INF;
int last_bad = walk_index(c[i], 1, 0, ssz-1, mn, mx);
ll val_bad = query_max(last_bad, last_bad, 1, 0, ssz-1); // value of the last bad range
ll final = query_max(ssz-1, ssz-1, 1, 0, ssz-1);
if (val_bad == mn){
// look at the upper wall
ll top_mx = query_max(last_bad, ssz-1, 1, 0, ssz-1);
ans[i] = c[i] - (top_mx-final);
}
else {
// look at the lower wall
ll bot_mn = query_min(last_bad, ssz-1, 1, 0, ssz-1);
ans[i] = final - bot_mn;
}
// process subtractions
for (auto&[tm,vl]:sub[i]){
upd_max(-vl, tm, ssz-1, 1, 0, ssz-1);
upd_min(-vl, tm, ssz-1, 1, 0, ssz-1);
}
}
return ans;
}
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}