#include <bits/stdc++.h>
#define Yang8on Nguyen_Dinh_Son
#define sonphamay Nguyen_Dinh_Son
#define aothtday "Sjeckanje"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define endl '\n'
#define pii pair<int, ll>
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define maxn 200005
#define maxm
#define maxx
#define mod 1000000007
#define base 311
#define ModHas 1000000003ll
#define gb(i, j) ((i >> j) & 1)
#define int long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, q;
ll a[maxn], d[maxn], dp[maxn];
struct dl
{
ll op_op, op_cl, cl_op, cl_cl;
void cb(dl x, dl y, int mid)
{
op_op = max(x.op_op + y.cl_op, x.op_cl + y.op_op);
op_cl = max(x.op_op + y.cl_cl, x.op_cl + y.op_cl);
cl_op = max(x.cl_op + y.cl_op, x.cl_cl + y.op_op);
cl_cl = max(x.cl_op + y.cl_cl, x.cl_cl + y.op_cl);
if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
{
op_op = max(x.op_op, x.op_cl) + max(y.op_op, y.cl_op);
op_cl = max(x.op_op, x.op_cl) + max(y.op_cl, y.cl_cl);
cl_op = max(x.cl_op, x.cl_cl) + max(y.cl_op, y.op_op);
cl_cl = max(x.cl_op, x.cl_cl) + max(y.op_cl, y.cl_cl);
}
}
} st[4 * maxn];
void built(int id = 1, int l = 1, int r = n - 1)
{
if(l == r)
{
st[id].op_op = abs(d[l]);
return ;
}
int mid = (l + r) >> 1;
built(id * 2, l, mid);
built(id * 2 + 1, mid + 1, r);
st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}
void update(int pos, int id = 1, int l = 1, int r = n - 1)
{
if(pos < l || r < pos) return ;
if(l == r)
{
st[id].op_op = abs(d[pos]), st[id].op_cl = st[id].cl_op = st[id].cl_cl = 0;
return ;
}
int mid = (l + r) >> 1;
update(pos, id * 2, l, mid);
update(pos, id * 2 + 1, mid + 1, r);
st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}
void solve()
{
cin >> n >> q;
fi(i, 1, n) cin >> a[i];
fi(i, 1, n - 1) d[i] = a[i] - a[i + 1];
// n = GetRandom(20, 20), q = GetRandom(10, 10);
// cout << n << ' ' << q << '\n';
// fi(i, 1, n) a[i] = GetRandom(1, 10), cout << a[i] << ' ' ;
// cout << '\n';
// fi(i, 1, n - 1) d[i] = a[i] - a[i + 1];
built();
fi(_, 1, q)
{
int l, r;
ll x;
cin >> l >> r >> x;
// l = GetRandom(1, n), r = GetRandom(1, n), x = GetRandom(1, 10);
// if(l > r) swap(l, r);
// cout << l << ' ' << r << ' ' << x << ' ' << "ANS" << ' ';
if(l - 1 != 0)
{
d[l - 1] -= x;
update(l - 1);
}
d[r] += x;
update(r);
cout << max({st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl}) << '\n';
// fi(i, l, r) a[i] += x;
// fi(i, 1, n) fi(j, 1, i) dp[i] = max(dp[i], abs(a[i] - a[j]) + dp[j - 1]);
//
// cout << dp[n] << ' ' << max({st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl}) << '\n';
//
// fi(i, 1, n) dp[i] = 0;
}
}
signed main()
{
if(fopen(aothtday".inp", "r"))
{
freopen(aothtday".inp","r",stdin);
freopen(aothtday".out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int nTest = 1;
// cin >> nTest;
while(nTest --)
{
solve();
}
return 0;
}
Compilation message
Main.cpp: In member function 'void dl::cb(dl, dl, long long int)':
Main.cpp:48:56: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
48 | if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
| ~~~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(aothtday".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen(aothtday".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6880 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6880 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 13 |
Correct |
244 ms |
30968 KB |
Output is correct |
| 14 |
Correct |
246 ms |
31056 KB |
Output is correct |
| 15 |
Correct |
272 ms |
31020 KB |
Output is correct |
| 16 |
Correct |
261 ms |
31200 KB |
Output is correct |
| 17 |
Correct |
250 ms |
30800 KB |
Output is correct |
| 18 |
Correct |
230 ms |
31680 KB |
Output is correct |
