#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+2;
int ar[N],it[4*N][2][2];
bool samesign(int a,int b){
if(a==0||b==0){
return true;
}
if(a>0&&b>0){
return true;
}
if(a<0&&b<0){
return true;
}
return false;
}
void pull(int idx,int l,int r){
int mid=(l+r)>>1;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
it[idx][i][j]=max(it[2*idx][i][0]+it[2*idx+1][1][j],max(it[2*idx][i][0]+it[2*idx+1][0][j],it[2*idx][i][1]+it[2*idx+1][0][j]));
if(samesign(ar[mid],ar[mid+1])){
it[idx][i][j]=max(it[idx][i][j],it[2*idx][i][1]+it[2*idx+1][1][j]);
}
}
}
}
void init(int idx,int l,int r){
if(l==r){
if(ar[l]<0){
it[idx][1][1]=-ar[l];
}
else{
it[idx][1][1]=ar[l];
}
return;
}
int mid=(l+r)>>1;
init(2*idx,l,mid);
init(2*idx+1,mid+1,r);
pull(idx,l,r);
}
void upd(int idx,int l,int r,int pos){
if(pos>r||pos<l){
return;
}
if(l==r){
if(ar[l]<0){
it[idx][1][1]=-ar[l];
}
else{
it[idx][1][1]=ar[l];
}
return;
}
int mid=(l+r)>>1;
upd(2*idx,l,mid,pos);
upd(2*idx+1 ,mid+1,r,pos);
pull(idx,l,r);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q,i,j,k,l;
cin>>n>>q;
if(n==1){
for(i=1;i<=q;i++){
cout<<0<<'\n';
}
return 0;
}
for(i=1;i<=n;i++){
cin>>j;
if(i>1){
ar[i-1]=j-k;
}
k=j;
}
n--;
init(1,1,n);
for(i=1;i<=n;i++){
cin>>j>>k>>l;
if(j>1){
ar[j-1]+=l;
upd(1,1,n,j-1);
}
if(k<=n){
ar[k]-=l;
upd(1,1,n,k);
}
/*
for(j=1;j<=n;j++){
cout<<ar[j]<<' ';
}
cout<<'\n';
*/
cout<<max(max(it[1][0][0],it[1][1][1]),max(it[1][0][1],it[1][1][0]))<<'\n';
}
}
/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
