// In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())
const ll maxn = 2e5 + 5;
const ll inf = 1e16 + 7;
ll n, q, a[maxn];
ll lazy[maxn << 2];
struct D{
ll ans, left, right, al, ar, is;
} node[maxn << 2];
D combine(D x, D y){
D res = {x.ans + y.ans, x.left, y.right, x.al, y.ar, 1};
if(x.right == y.left) return res;
if(x.right > y.left){
ll delta = x.right - y.left;
if(x.ar != -inf && x.ar < x.right) delta -= abs(x.ar - x.right);
if(y.al != -inf && y.al > y.left) delta -= abs(y.al - y.left);
if(delta <= 0) return res;
res.ans += delta;
if(!x.is){
if(x.al == -inf) res.al = y.left;
else if(x.al == x.right){
if(x.left < x.right) res.al = -inf;
}
}
if(!y.is){
if(y.ar == -inf) res.ar = x.right;
else if(y.ar == y.left){
if(y.right > y.left) res.ar = -inf;
}
}
if(x.is == 0 && y.is == 0){
if(x.ar == -inf || x.ar > x.right){
if(y.al == -inf || y.al < x.left) res.is = 0;
}
}
}
if(x.right < y.left){
ll delta = abs(x.right - y.left);
if(x.ar != -inf && x.ar > x.right) delta -= abs(x.ar - x.right);
if(y.al != -inf && y.al < y.left) delta -= abs(y.al - y.left);
if(delta <= 0) return res;
res.ans += delta;
if(!x.is){
if(x.al == -inf) res.al = y.left;
else if(x.al == x.right){
if(x.left > x.right) res.al = -inf;
}
}
if(!y.is){
if(y.ar == -inf) res.ar = x.right;
else if(y.ar == y.left){
if(y.right < y.left) res.ar = -inf;
}
}
if(x.is == 0 && y.is == 0){
if(x.ar == -inf || x.ar < x.right){
if(y.al == -inf || y.al > x.left) res.is = 0;
}
}
}
return res;
}
void build(ll l = 0, ll r = n, ll id = 1){
if(l == r - 1){
node[id].ans = 0;
node[id].left = a[l];
node[id].right = a[l];
node[id].al = -inf;
node[id].ar = -inf;
node[id].is = 0;
return;
}
ll mid = (l + r) / 2;
build(l, mid, id * 2);
build(mid, r, id * 2 + 1);
node[id] = combine(node[id * 2], node[id * 2 + 1]);
}
void change(ll x, ll id){
node[id].right += x;
node[id].left += x;
if(node[id].al != -inf) node[id].al += x;
if(node[id].ar != -inf) node[id].ar += x;
lazy[id] += x;
}
void relax(ll id){
change(lazy[id], id * 2);
change(lazy[id], id * 2 + 1);
lazy[id] = 0;
}
void upd(ll s, ll e, ll x, ll l = 0, ll r = n, ll id = 1){
if(s <= l && r <= e){
change(x, id);
return;
}
if(e <= l || r <= s) return;
ll mid = (l + r) / 2;
relax(id);
upd(s, e, x, l, mid, id * 2);
upd(s, e, x, mid, r, id * 2 + 1);
node[id] = combine(node[id * 2], node[id * 2 + 1]);
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for(ll i = 0; i < n; i++) cin >> a[i];
build();
while(q--){
ll l, r, x; cin >> l >> r >> x;
l--;
upd(l, r, x);
cout << node[1].ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
