#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
int n, Q;
int A[maxn];
int diff[maxn];
struct dat {
int v, vs, ve;
int ss, se;
dat () {}
dat (int nv) {
v = vs = ve = abs(nv);
ss = se = (nv < 0);
}
void merge(const dat &a, const dat &b) {
v = a.v + b.v;
if (a.se != b.ss) v -= min(a.ve, b.vs);
vs = a.vs;
ve = b.ve;
ss = a.ss;
se = b.se;
}
};
struct node {
int s, m, e;
dat d;
node *l, *r;
node (int _s, int _e) {
s = _s; e = _e; m = (s+e)/2;
if (s != e) {
l = new node(s,m);
r = new node(m+1,e);
d.merge(l -> d, r -> d);
// cout << s << " " << e << " " << d.v << "\n";
} else {
diff[s] = A[s] - A[s-1];
d = dat(A[s] - A[s-1]);
}
}
void upd(int x, int nv) {
if (s == e) {
d = dat(nv);
} else {
if (x > m) r -> upd(x,nv);
else if (x <= m) l -> upd(x,nv);
d.merge(l -> d, r -> d);
// cout << "UPD: " << s << " " << e << " " << d.v << "\n";
}
}
int rmq() {
return d.v;
}
} *root;
int32_t main() {
FAST
// ifstream cin("input.txt");
cin >> n >> Q;
for (int i =1;i<=n;i++) cin >> A[i];
A[0] = A[1];
root = new node(1,n);
// cout << root -> rmq() << "\n";
for (int q = 0; q<Q;q++) {
int l, r, x; cin >> l >> r >> x;
if (l != 1) {
diff[l] += x;
root -> upd(l, diff[l]);
}
if (r+1 <= n) {
diff[r + 1] -= x;
root -> upd(r+1, diff[r+1]);
}
// for (int i =1;i<=n;i++) cout << diff[i] << " ";
// cout << "\n";
cout << root -> rmq() << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
