#include "candies.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
struct lazy_segment_tree{
ll N;
ll log;
vi sum, max, min;
vi lsum, lmax, lmin;
lazy_segment_tree(ll n){
N = 1;
log = 0;
while(N <= n){
N *= 2;
log++;
}
sum.resize(2*N);
max.resize(2*N);
min.resize(2*N);
lsum.resize(2*N);
lmax.resize(2*N);
lmin.resize(2*N);
}
void update(ll a, ll b, ll val){
ll l = a+N, r = b+N-1;
per(i,log,0){
eval(l>>i);
eval(r>>i);
}
while(l < r){
if(l & 1){
lmax[l] = std::max(lmax[l], lsum[l]+val);
lmin[l] = std::min(lmin[l], lsum[l]+val);
lsum[l] += val;
l++;
}
l >>= 1;
if((r&1) == 0){
lmax[r] = std::max(lmax[r], lsum[r]+val);
lmin[r] = std::min(lmin[r], lsum[r]+val);
lsum[r] += val;
r--;
}
r >>= 1;
}
if(l == r){
lmax[l] = std::max(lmax[l], lsum[l]+val);
lmin[l] = std::min(lmin[l], lsum[l]+val);
lsum[l] += val;
}
}
/*void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(r <= a || b <= l) return;
eval(now);
if(a <= l && r <= b){
if(val > 0) lmax[now] = val;
else lmin[now] = val;
lsum[now] += val;
return;
}
update(a,b,val,now*2,l,(l+r)/2);
update(a,b,val,now*2+1,(l+r)/2,r);
}*/
pii calc(ll now){
now += N;
per(i,log,0){
eval(now>>i);
}
return mp(max[now], min[now]);
}
void eval(ll now){
/*if(lmax[now]){
max[now] = std::max(max[now], sum[now]+lmax[now]);
if(now < N){
lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
}
lmax[now] = 0;
}
if(lmin[now]){
min[now] = std::min(min[now], sum[now]+lmin[now]);
if(now < N){
lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
}
lmin[now] = 0;
}
if(lsum[now]){
sum[now] += lsum[now];
if(now < N){
lsum[now*2] += lsum[now];
lsum[now*2+1] += lsum[now];
}
lsum[now] = 0;
}
lmax[now] = lmin[now] = lsum[now] = 0;
}*/
max[now] = std::max(max[now], sum[now]+lmax[now]);
min[now] = std::min(min[now], sum[now]+lmin[now]);
sum[now] += lsum[now];
if(now < N){
lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
lsum[now*2] += lsum[now];
lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
lsum[now*2+1] += lsum[now];
}
lmax[now] = lmin[now] = lsum[now] = 0;
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int N = c.size();
ll Q = l.size();
vi left(N,-1), right(N,Q);
while(true){
lazy_segment_tree seg(N);
vi mid(N);
bool flg = true;
vii query(Q+1);
rep(i,0,N){
if(left[i]+1 < right[i]){
mid[i] = (left[i]+right[i])/2;
query[mid[i]].pb(i);
flg = false;
}
}
if(flg) break;
per(i,Q,0){
if(i < Q){
seg.update(l[i], r[i]+1, v[i]);
}
for(auto el: query[i]){
auto ret = seg.calc(el);
if(c[el] <= ret.first-ret.second) left[el] = mid[el];
else right[el] = mid[el];
}
}
}
vector<int> ans(N);
{
vii max(Q+1), min(Q+1);
rep(i,0,N){
if(left[i] == -1) max[0].pb(i);
else{
if(v[left[i]] > 0){
min[left[i]].pb(i);
}
else{
max[left[i]].pb(i);
}
}
}
lazy_segment_tree seg(N);
per(i,Q,0){
if(i < Q){
seg.update(l[i], r[i]+1, v[i]);
}
for(auto el: max[i]){
ans[el] = seg.calc(el).first;
}
for(auto el: min[i]){
ans[el] = c[el]+seg.calc(el).second;
}
}
}
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;
}
Compilation message
candies.cpp:217:1: error: expected '}' at end of input
217 | }
| ^
candies.cpp:24:25: note: to match this '{'
24 | struct lazy_segment_tree{
| ^
candies.cpp:217:1: error: expected unqualified-id at end of input
217 | }
| ^
