#include<bits/stdc++.h>
using namespace std;
long long c[200010];
struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];
void push(int w){
if(w>=base)return;
tree[w*2].lazy+=tree[w].lazy;
tree[w*2+1].lazy+=tree[w].lazy;
tree[w*2].mini+=tree[w].lazy;
tree[w*2].maxi+=tree[w].lazy;
tree[w*2+1].mini+=tree[w].lazy;
tree[w*2+1].maxi+=tree[w].lazy;
tree[w].lazy = 0;
}
void update(int w, int l, int p, int a, int b, long long val){
push(w);
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w].lazy+=val;
tree[w].maxi+=val;
tree[w].mini+=val;
return;
}
update(w*2, l, (l+p)/2, a, b, val);
update(w*2+1, (l+p)/2+1, p, a, b, val);
tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long maxi(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return -1000000000000000000;
if(a<=l && p<=b){
return tree[w].maxi;
}
return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long mini(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return 1000000000000000000;
if(a<=l && p<=b){
return tree[w].mini;
}
return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
int main()
{
int n, q, i, a, b, v;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%lld", &c[i]);
scanf("%d", &q);
vector<pair<int,pair<int,int>>>sorted;
for(i=1;i<=q;i++){
scanf("%d%d%d", &a, &b, &v);
sorted.push_back({a, {i, v}});
sorted.push_back({b+1, {i, -v}});
}
for(i=q+1;i<base;i++){
tree[base+i].mini = 1000000000000000000;
tree[base+i].maxi = -1000000000000000000;
}
for(i=base-1;i>0;i--){
tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
}
sort(sorted.begin(), sorted.end());
int it = 0;
for(i=0;i<n;i++){
while(it<(int)sorted.size() && sorted[it].first==i){
update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
it++;
}
int p;
if(tree[1].maxi-tree[1].mini>=c[i]){
int w = 1;
long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
while(w<base){
push(w);
if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
w = w*2+1;
else{
sufMAX = max(sufMAX, tree[w*2+1].maxi);
sufMIN = min(sufMIN, tree[w*2+1].mini);
w = w*2;
}
}
p = w-base;
}
else{
p = -1;
}
if(p==-1)
printf("%lld ", mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
else{
if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
printf("%lld ", mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
else
printf("%lld ", mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
}
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
candies.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%lld", &c[i]);
| ~~~~~^~~~~~~~~~~~~~~
candies.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
candies.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d%d%d", &a, &b, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccy264Ri.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6FVXNi.o:candies.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccy264Ri.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
