#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const int SS=1<<18;
const ll INF=1e18;
struct node{
ll m[3][3];
bool sg;
};
node seg[(SS<<1)+1],em;
ll lazy[(SS<<1)+1];
//1-min // 2-max //0-(max/min)-ja
void add(int ind,ll x){
if(seg[ind].m[0][0]=-INF) seg[ind].m[0][0]=0;
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
seg[ind].m[i][j]-=((i==1)+(j==1))*x;
seg[ind].m[i][j]+=((i==2)+(j==2))*x;
if(seg[ind].sg and i!=0 and j!=0) seg[ind].m[i][j]=-INF;
}
}
}
node comb(node a,node b){
if(a.m[0][0]==-INF) return b;
if(b.m[0][0]==-INF) return a;
node res;
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
res.m[i][j]=-INF;
for(int k=0;k<=2;k++) res.m[i][j]=max(res.m[i][j],a.m[i][k]+b.m[(3-k)%3][j]);
res.m[i][j]=max({res.m[i][j],a.m[i][j],b.m[i][j]});
}
}
return res;
}
void push(int v){
if(lazy[v]==0) return;
lazy[v<<1]+=lazy[v],lazy[(v<<1)+1]+=lazy[v];
add(v<<1,lazy[v]),add((v<<1)+1,lazy[v]);
lazy[v]=0;
}
void Insert(int pocz,int kon,int x,int p=0,int k=SS-1,int v=1){
if(p>kon or k<pocz) return;
if(p>=pocz and k<=kon) add(v,x),lazy[v]+=x;
else{
push(v);
Insert(pocz,kon,x,p,(p+k)>>1,v<<1),Insert(pocz,kon,x,((p+k)>>1)+1,k,(v<<1)+1);
seg[v]=comb(seg[v<<1],seg[(v<<1)+1]);
}
}
node Query(int pocz,int kon,int p=0,int k=SS-1,int v=1){
if(p>kon or k<pocz) return em;
if(p>=pocz and k<=kon) return seg[v];
push(v);
return comb(Query(pocz,kon,p,(p+k)>>1,v<<1),Query(pocz,kon,((p+k)>>1)+1,k,(v<<1)+1));
}
void solve(){
em.m[0][0]=-INF;
for(int i=1;i<=(SS<<1);i++) seg[i].m[0][0]=-INF;
for(int i=SS;i<=(SS<<1);i++) seg[i].sg=1;
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
int a;
cin>>a;
if(a==0) Insert(i,i,1),Insert(i,i,-1);
else Insert(i,i,a);
}
while(q--){
int a,b,c;
cin>>a>>b>>c;
Insert(a,b,c);
cout<<seg[1].m[0][0]<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
Compilation message
Main.cpp: In function 'void add(int, ll)':
Main.cpp:19:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
19 | if(seg[ind].m[0][0]=-INF) seg[ind].m[0][0]=0;
| ~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
41300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
41300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
41300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
