#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<lld,null_type,less<lld>,rb_tree_tag,tree_order_statistics_node_update> order_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const lld INF=1e18;
class ST{
public:
lld arr[1000000][3][3];
lld lazy[1000000];
void propag(int a, int b, int node){
if(lazy[node]!=0){
rep(i,0,3){
rep(j,0,3){
arr[node][i][j]+=lazy[node]*((i==1)-(i==2)+(j==1)-(j==2));
}
}
if(a!=b){
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
lazy[node]=0;
}
}
void combine(int a, int b, int node){
rep(i,0,3){
rep(j,0,3)arr[node][i][j]=-INF;
}
rep(i,0,3){
rep(j,0,3){
rep(k,0,3){
rep(l,0,3){
if((j+k)%3==0){
arr[node][i][l]=max(arr[node][i][l],arr[2*node][i][j]+arr[2*node+1][k][l]);
}
}
}
}
}
}
void init(int a, int b, int node){
if(a==b){
rep(i,0,3){
rep(j,0,3)arr[node][i][j]=0;
}
rep(i,1,3){
rep(j,1,3)arr[node][i][j]=-INF;
}
lazy[node]=0;
return;
}
int mid=(a+b)/2;
init(a,mid,2*node);
init(mid+1,b,2*node+1);
combine(a,b,node);
}
void update(int a, int b, int node, int l, int r, lld val){
propag(a,b,node);
if(r<a || b<l)return;
if(l<=a && b<=r){
lazy[node]+=val;
propag(a,b,node);
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,l,r,val);
update(mid+1,b,2*node+1,l,r,val);
combine(a,b,node);
}
/*lld query(int a,int b, int node, int l, int r){
if(r<a || b<l)return INF;
if(l<=a && b<=r)return arr[node];
int mid=(a+b)/2;
return min(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
}*/
void print(int a, int b, int node){
cout<<a<<" "<<b<<" "<<lazy[node]<<endl;
rep(i,0,3){
rep(j,0,3)cout<<arr[node][i][j]<<" ";
cout<<endl;
}cout<<endl;
if(a==b)return;
int mid=(a+b)/2;
print(a,mid,2*node);
print(mid+1,b,2*node+1);
}
};
lld arr[1000000];
ST S;
void solve(){
int n,q;
cin>>n>>q;
S.init(0,n-1,1);
rep(i,0,n)cin>>arr[i],S.update(0,n-1,1,i,i,arr[i]);
while(q--){
int l,r;
lld x;
cin>>l>>r>>x;
l--;r--;
S.update(0,n-1,1,l,r,x);
S.propag(0,n-1,1);
cout<<S.arr[1][0][0]<<"\n";
//S.print(0,n-1,1);
}
}
int main(){
int tt;
tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
