#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int mod = 1e9 + 7;
struct node{
int mn, mx, lazy, cnt_mn, cnt_mx;
};
node UND = {mod, -mod, 0, 0, 0};
struct Segtree{
int n;
vector<node> t;
Segtree(int sz){
n = sz;
t.resize(n * 4, UND);
};
node merge(node A, node B){
int m1 = A.cnt_mn + B.cnt_mn, m2 = A.cnt_mx + B.cnt_mx;
if(A.mx > B.mx) m2-= B.cnt_mx;
if(B.mx > A.mx) m2-= A.cnt_mx;
if(A.mn < B.mn) m1-= B.cnt_mn;
if(B.mn < A.mn) m1-= A.cnt_mn;
return {min(A.mn, B.mn), max(A.mx, B.mx), A.lazy + B.lazy, m1, m2};
}
void build(vector<int> &a, int v, int vl, int vr){
if(vl == vr){
t[v] = {a[vl], a[vl], 0, 1, 1};
}else{
int mid = (vl + vr)>>1;
build(a, v<<1, vl, mid);
build(a, v<<1|1, mid+1, vr);
t[v] = merge(t[v<<1], t[v<<1|1]);
}
}
void push(int v, int vl, int vr){
if(!t[v].lazy) return;
t[v].mn+= t[v].lazy;
t[v].mx+= t[v].lazy;
if(vl != vr){
t[v<<1].lazy+= t[v].lazy;
t[v<<1|1].lazy+= t[v].lazy;
}
t[v].lazy = 0;
}
void add(int l, int r, int x, int v, int vl, int vr){
push(v, vl, vr);
if(l > vr or vl > r) return;
if(l <= vl and r >= vr){
t[v].lazy+= x;
push(v, vl, vr);
return;
}
int mid = (vl + vr)>>1;
add(l, r, x, v<<1, vl, mid);
add(l, r, x, v<<1|1, mid+1, vr);
t[v] = merge(t[v<<1], t[v<<1|1]);
}
node get(int l, int r, int v, int vl, int vr){
push(v, vl, vr);
if(l > vr or vl > r) return UND;
if(l <= vl and r >= vr) return t[v];
int mid = (vl + vr)>>1;
return merge(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
}
};
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n+1);
for(int i = 1;i <= n; i++){
cin >> a[i];
}
Segtree tree(n+1);
tree.build(a, 1, 1, n);
while(q--){
int l, r, x; cin >> l >> r >> x;
tree.add(l, r, x, 1, 1, n);
node res = tree.get(1, n, 1, 1, n);
int c = min(res.cnt_mx, res.cnt_mn);
cout << (res.mx * c) - (res.mn * c) << '\n';
}
return 0;
}
Compilation message
Main.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
78 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
