#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb pusi_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "sjeckanje"
int n, q;
const int N = 2e5;
ll a[N + 5];
ll dp[N + 5][3];
int solve(){
dp[0][0] = 0;
dp[0][1] = dp[0][2] = -1e15;
fod(i,1,n){
dp[i][0] = max({dp[i-1][1] - a[i], dp[i-1][2] + a[i], dp[i-1][0]});
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
dp[i][2] = max(dp[i-1][2], dp[i-1][0] - a[i]);
}
return dp[n][0];
}
int d[N + 5];
int st[4 * N][2][2];
void upd(int u, int i = 1, int l = 1, int r = n - 1){
if(r < u or u < l) return;
if(l == r){
st[i][1][1] = abs(d[l]);
return;
}
int mid = l + r >> 1;
upd(u,i<<1,l,mid);
upd(u,i<<1|1,mid+1,r);
st[i][1][1] = max(st[i<<1][1][0] + st[i<<1|1][1][1], st[i<<1][1][1] + st[i<<1|1][0][1]);
st[i][1][0] = max(st[i<<1][1][0] + st[i<<1|1][1][0], st[i<<1][1][1] + st[i<<1|1][0][0]);
st[i][0][1] = max(st[i<<1][0][0] + st[i<<1|1][1][1], st[i<<1][0][1] + st[i<<1|1][0][1]);
st[i][0][0] = max(st[i<<1][0][0] + st[i<<1|1][1][0], st[i<<1][0][1] + st[i<<1|1][0][0]);
if((d[mid] >= 0 and d[mid + 1] >= 0) or (d[mid] <= 0 and d[mid + 1] <= 0)){
st[i][1][1] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]);
st[i][1][0] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]);
st[i][0][1] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]);
st[i][0][0] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
fod(i,1,n) cin >> a[i];
fod(i,1,n-1){
d[i] = a[i+1] - a[i];
upd(i);
}
while(q--){
int l, r, x;
cin >> l >> r >> x;
// fod(i,l,r) a[i] += x;
// cout << solve() << el;
d[r] -= x;
upd(r);
if(l-1){
d[l-1] += x;
upd(l-1);
}
cout << max(max(st[1][0][0], st[1][1][1]), max(st[1][0][1], st[1][1][0])) << el;
}
return 0;
}
Compilation message
Main.cpp: In function 'void upd(int, int, int, int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
