#include<bits/stdc++.h>
using namespace std;
#define int long long
long long n, q, a[200001];
pair<int, pair<int, int>> tree[1000001];
void build(int id, int l, int r)
{
if(l == r)
{
tree[id] = {0, {a[l], a[l]}};
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
tree[id].second.first = max(tree[id * 2].second.first, tree[id * 2 + 1].second.first);
tree[id].second.second = min(tree[id * 2].second.second, tree[id * 2 + 1].second.second);
tree[id].first = max(tree[id * 2].first + tree[id * 2 + 1].first, max(tree[id * 2].second.first, tree[id * 2 + 1].second.first) - min(tree[id * 2].second.second, tree[id * 2 + 1].second.second));
}
void update(int id, int l, int r, int posl, int posr, int val)
{
if(posr < l || posl > r) return;
if(r == l)
{
tree[id].second.first += val;
tree[id].second.second += val;
tree[id].first = 0;
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, posl, posr, val);
update(id * 2 + 1, mid + 1, r, posl, posr, val);
tree[id].second.first = max(tree[id * 2].second.first, tree[id * 2 + 1].second.first);
tree[id].second.second = min(tree[id * 2].second.second, tree[id * 2 + 1].second.second);
tree[id].first = max(tree[id * 2].first + tree[id * 2 + 1].first, max(tree[id * 2].second.first, tree[id * 2 + 1].second.first) - min(tree[id * 2].second.second, tree[id * 2 + 1].second.second));
}
signed main()
{
cin >> n >> q;
for(int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while(q--)
{
long long x, y, z;
cin >> x >> y >> z;
update(1, 1, n, x, y, z);
cout << tree[1].first << "\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 |
- |
