#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define yes cout << "YES\n"
#define no cout << "NO\n"
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const ll N = 1 << 18;
struct item
{
ll ans;
ll x, y;
item()
{
x = 0, y = 0;
ans = 0;
}
};
item t[2 * N + 5];
ll a[N];
ll b[N];
ll n, m, k, mod = 1e9 + 7;
void upd(ll i, ll l, ll r)
{
ll x = b[t[i * 2 + 1].x];
ll y = b[t[i * 2].y];
if((r + l) / 2 == l)
y = 0;
if(x * y < 0)
x = max(0LL, abs(x) - abs(y));
t[i].ans = ((l + r) / 2 != l ? t[i * 2].ans : 0) + ((l + r) / 2 + 1 != r ? t[i * 2 + 1].ans : 0) + abs(x);
t[i].x = t[i * 2].x;
t[i].y = t[i * 2 + 1].y;
}
void build(ll i = 1, ll l = 1, ll r = n)
{
if(l == r)
{
t[i].ans = abs(b[l]);
t[i].x = t[i].y = l;
return;
}
ll mid = (l + r) >> 1;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
upd(i, l, r);
}
void change(ll l, ll r, ll x, ll l1 = 1, ll r1 = n, ll v = 1)
{
if(l1 > r || r1 < l)
return;
if(l <= l1 && r1 <= r)
{
t[v].ans = abs(x);
return;
}
ll mid = (l1 + r1) / 2;
change(l, r, x, l1, mid, v * 2), change(l, r, x, mid + 1, r1, v * 2 + 1);
upd(v, l1, r1);
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> n >> m;
for(ll i = 1; i <= n; ++i)
cin >> a[i];
for(ll i = 1; i <= n; ++i)
b[i] = a[i] - a[i - 1];
build();
for(ll i = 1, l, r, x; i <= m; ++i)
cin >> l >> r >> x, b[r + 1] -= x, b[l] += x, change(r + 1, r + 1, b[r + 1]), change(l, l, b[l]), cout << t[1].ans << "\n";
}
Compilation message
Main.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
75 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
