#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> pr;
ll cap,n;
vi lazy;
vector<pr> seg; //min,max
void psh(ll v){
lazy[v*2] += lazy[v],
lazy[v*2+1] += lazy[v];
seg[v*2].first += lazy[v];
seg[v*2].second += lazy[v];
seg[v*2+1].first += lazy[v];
seg[v*2+1].second += lazy[v];
lazy[v] = 0;
}
void correct(ll v,ll tl,ll tr){
if(tl==tr){
if(seg[v].first< 0) seg[v].first=0;
if(seg[v].second>cap)seg[v].first=cap;
return;
}
psh(v);
ll tm=(tl+tr)/2;
if(seg[v].first >= 0 && seg[v].second <= cap) return;
if(seg[v].second < 0){
seg[v].first+=-seg[v].second;
seg[v].second=0;
correct(v*2,tl,tm);
correct(v*2+1,tm+1,tr);
}
if(seg[v].first > cap){
seg[v].second+= -seg[v].first;
seg[v].first=cap;
correct(v*2,tl,tm);
correct(v*2+1,tm+1,tr);
}
}
void update(ll v,ll l,ll r,ll tl,ll tr,ll add){
if(l > r) return;
psh(v);
if(tl==l && tr==r){
seg[v].first +=add;
seg[v].second+=add;
lazy[v]+=add;
return;
}
ll tm=(tl+tr)/2;
update(v*2,l,min(r,tm),tl,tm,add);
update(v*2+1,max(l,tm+1),r,tm+1,tr,add);
seg[v].first = min(seg[v*2].first,seg[v*2+1].first);
seg[v].second = max(seg[v*2].second,seg[v*2+1].second);
}
ll query(ll v,ll tl,ll tr,ll node){
if(tl==tr) return seg[v].first;
ll tm=(tl+tr)/2;
psh(v);
if(node<=tm) return query(v*2,tl,tm,node);
else return query(v*2+1,tm+1,tr,node);
}
vector<int> distribute_candies(vector<int> c,
vector<int> l, vector<int> r, vector<int> v){
cap = c[0],n=c.size();
seg.resize(4*n+100,{0,0}),lazy.resize(4*n+100,0);
for(ll i = 0; i < l.size();i++){
update(1,l[i]+1,r[i]+1,1,n,v[i]);
correct(1,1,n);
}
vector<int> ret(n,0);
for(ll i = 0; i < n;i++)
ret[i] = query(1,1,n,i+1);
return ret;
}
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 < (int)ans.size(); ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
Compilation message
candies.cpp:84:1: error: extended character is not valid in an identifier
84 |
| ^
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:74:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(ll i = 0; i < l.size();i++){
| ~~^~~~~~~~~~
candies.cpp: At global scope:
candies.cpp:84:1: error: '\U000000a0' does not name a type
84 |
| ^
