#include<bits/stdc++.h>
using namespace std;
const int N=1<<3;
typedef long long ll;
ll tab[N];
int lew[N+N], pra[N+N];
ll dp[2][2][N+N];
int red(ll a){
if(a==0)return 0;
return a/abs(a);
}
void upd(int v){
if(v>=N){
dp[0][0][v]=dp[1][0][v]=dp[0][1][v]=0;
dp[1][1][v]=abs(tab[v-N]);
return;
}
int L=lew[v], R=pra[v], M=(L+R)>>1;
int l=2*v, r=2*v+1;
if(red(tab[M])*red(tab[M+1])<0){
//cout<<v<<"a\n";
for(int x=0; x<2; x++){
for(int y=0; y<2; y++){
dp[x][y][v]=0;
for(int i=0; i<2; i++){
for(int j=0; j+i<2; j++){
dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]);
}
}
}
}
}
else{
//cout<<v<<"b\n";
for(int x=0; x<2; x++){
for(int y=0; y<2; y++){
dp[x][y][v]=0;
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]);
}
}
}
}
}
}
void construct(){
for(int i=N; i<N+N; i++){
lew[i]=i-N;
pra[i]=i-N;
upd(i);
}
for(int i=N-1; i>0; i--){
lew[i]=lew[2*i];
pra[i]=pra[2*i+1];
upd(i);
}
}
int n, q;
void ust(int i, int x){
if(i==0 || i==n)return;
tab[i]=x;
i+=N;
while(i>0){
upd(i);
i/=2;
}
}
void out(){
for(int i=0; i<=n; i++)cout<<tab[i]<<" ";
cout<<"\n";
for(int i=1; i<N+N; i++){
cout<<i<<" "<<dp[0][0][i]<<" "<<dp[0][1][i]<<" "<<dp[1][0][i]<<" "<<dp[1][1][i]<<"\n";
}
cout<<"\n";
}
int main(){
cin>>n>>q;
int p;
cin>>p;
for(int i=1; i<n; i++){
int pp;
cin>>pp;
tab[i]=pp-p;
p=pp;
}
construct();
while(q--){
int l, r, d;
cin>>l>>r>>d;
ust(l-1, tab[l-1]+d);
ust(r, tab[r]-d);
//out();
cout<<max({dp[0][0][1], dp[0][1][1], dp[1][1][1], dp[1][0][1]})<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
