#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;
const ll mod = 1e9 + 7, MOD = 998244353;
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(name.size()){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
struct item{
ll l, r, dp[2][2];
};
struct segtree{
int size;
vector<item> values;
item neut = {0, 0, {{0,0}, {0,0}}};
void init(int n){
size = 1;
while(size < n) size *= 2;
values.assign(2 * size, neut);
}
item single (int v) {
return {v, v, {{0, 0}, {0, abs(v)}}};
}
item merge(item &x, item &y) {
item res;
res.l = x.l;
res.r = y.r;
F0R(l, 2) F0R(r, 2) {
res.dp[l][r] = 0;
F0R(o, 2) F0R(m, 2) {
if(m == 1 && o == 1 && (x.r >= 0) != (y.l >= 0)) continue;
res.dp[l][r] = max(res.dp[l][r], x.dp[l][m] + y.dp[o][r]);
}
}
return res;
}
void build(vector<ll> &a, int x, int lx, int rx) {
if(rx - lx == 1) {
if(lx < (int)a.size()) {
values[x] = single(a[lx]);
}
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
}
void build(vector<ll> &a) {
build(a, 0, 0, size);
}
void set(int i, ll v, int x, int lx, int rx){
if(rx - lx == 1){
values[x] = single(v);
return;
}
int m = (lx + rx) / 2;
if(i < m){
set(i, v, 2 * x + 1, lx, m);
} else {
set(i, v, 2 * x + 2, m, rx);
}
values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
}
void set(int i, ll v){
set(i, v, 0, 0, size);
}
item calc(int l, int r, int x, int lx, int rx){
if(lx >= r || rx <= l) return neut;
if(l <= lx && r >= rx) return values[x];
int m = (lx + rx) / 2;
item s1 = calc(l, r, 2 * x + 1, lx, m);
item s2 = calc(l, r, 2 * x + 2, m, rx);
return merge(s1, s2);
}
item calc(int l, int r){
return calc(l, r, 0, 0, size);
}
};
int main()
{
setIO();
int n, q; cin >> n >> q;
vector<ll> a(n), d(n-1);
F0R(i, n) cin >> a[i];
F0R(i, n-1) {
d[i] = a[i+1] - a[i];
}
segtree S;
S.init(n-1);
S.build(d);
//item res = S.values[0];
/*int mx = 0;
F0R(i, 2) F0R(j, 2) {
mx = max(mx, res.dp[i][j]);
}
cout << mx << '\n';*/
//cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
while(q--) {
ll l, r, x;
cin >> l >> r >> x;
l -= 2;
r--;
if(l >= 0) {d[l] = d[l] + x; S.set(l, d[l]);}// cout << d[l] << " ";}
if(r < n-1){d[r] = d[r] - x; S.set(r, d[r]);}
//cout << d[r ] << " ";}
//cout << d[l] << d[r] << " ";
item res = S.values[0];
ll mx = 0;
F0R(i, 2) F0R(j, 2) {
mx = max(mx, res.dp[i][j]);
}
cout << mx << "\n";
//cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((name+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen((name+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
320 KB |
Output is correct |
| 7 |
Correct |
3 ms |
852 KB |
Output is correct |
| 8 |
Correct |
4 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
836 KB |
Output is correct |
| 11 |
Correct |
4 ms |
852 KB |
Output is correct |
| 12 |
Correct |
4 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
320 KB |
Output is correct |
| 7 |
Correct |
3 ms |
852 KB |
Output is correct |
| 8 |
Correct |
4 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
836 KB |
Output is correct |
| 11 |
Correct |
4 ms |
852 KB |
Output is correct |
| 12 |
Correct |
4 ms |
896 KB |
Output is correct |
| 13 |
Correct |
407 ms |
37224 KB |
Output is correct |
| 14 |
Correct |
425 ms |
37204 KB |
Output is correct |
| 15 |
Correct |
409 ms |
37108 KB |
Output is correct |
| 16 |
Correct |
394 ms |
37096 KB |
Output is correct |
| 17 |
Correct |
443 ms |
37040 KB |
Output is correct |
| 18 |
Correct |
370 ms |
37728 KB |
Output is correct |
