#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 1000;
vector<int> a(N);
vector<pair<int, int>> t(4 * N);
vector<int> lazy(4 * N);
void push(int v, int vl, int vr){
if (lazy[v]){
t[2 * v].first += lazy[v];
t[2 * v].second+= lazy[v];
t[2 * v + 1].first += lazy[v];
t[2 * v + 1].second+= lazy[v];
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
}
void build(int v, int vl, int vr) {
if (vl == vr) {
t[v] = {a[vl], a[vl]};
return;
}
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
t[v] = {max(t[2 * v].first, t[2 * v + 1].first), min(t[2 * v].second, t[2 * v + 1].second)};
}
void update(int v, int vl, int vr, int l, int r, int x){
if (vl > r || vr < l) return;
if (vl >= l && vr <= r){
t[v].first += x;
t[v].second += x;
lazy[v] += x;
return;
}
push(v, vl ,vr);
int vm = (vl + vr) / 2;
update(2 * v, vl, vm, l, r, x);
update(2 * v + 1, vm + 1, vr, l, r, x);
t[v] = {max(t[2 * v].first, t[2 * v + 1].first), min(t[2 * v].second, t[2 * v + 1].second)};
}
int get(int v, int vl, int vr, int l, int r){
if (vl > r || vr < l) return 0;
push(v, vl, vr);
int node = t[v].first - t[v].second;
int izq = t[2 * v].first - t[2 * v].second;
int der = t[2 * v + 1].first - t[2 * v + 1].second;
if (vr - vl == 1 || node > izq + der){
return node;
}else{
int vm = (vl + vr) / 2;
if (vl < vm) izq = get(2 * v, vl, vm, l, r);
if (vm + 1 < vr) der = get(2 * v + 1, vm + 1, vr, l, r);
return izq + der;
}
}
signed main()
{
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> a[i];
}
build(1, 0, n - 1);
while(m--){
int l, r, x;
cin >> l >> r >> x;
l--; r--;
update(1,0 , n - 1, l, r, x);
cout << get(1,0 , n - 1, 0, n - 1) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
