#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]),seg[v].sg=0;
}
}
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();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
41300 KB |
Output is correct |
2 |
Correct |
23 ms |
41304 KB |
Output is correct |
3 |
Correct |
19 ms |
41360 KB |
Output is correct |
4 |
Correct |
18 ms |
41300 KB |
Output is correct |
5 |
Correct |
19 ms |
41356 KB |
Output is correct |
6 |
Correct |
19 ms |
41308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
41300 KB |
Output is correct |
2 |
Correct |
23 ms |
41304 KB |
Output is correct |
3 |
Correct |
19 ms |
41360 KB |
Output is correct |
4 |
Correct |
18 ms |
41300 KB |
Output is correct |
5 |
Correct |
19 ms |
41356 KB |
Output is correct |
6 |
Correct |
19 ms |
41308 KB |
Output is correct |
7 |
Correct |
33 ms |
41564 KB |
Output is correct |
8 |
Correct |
32 ms |
41548 KB |
Output is correct |
9 |
Correct |
32 ms |
41500 KB |
Output is correct |
10 |
Correct |
31 ms |
41536 KB |
Output is correct |
11 |
Correct |
35 ms |
41584 KB |
Output is correct |
12 |
Correct |
29 ms |
41516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
41300 KB |
Output is correct |
2 |
Correct |
23 ms |
41304 KB |
Output is correct |
3 |
Correct |
19 ms |
41360 KB |
Output is correct |
4 |
Correct |
18 ms |
41300 KB |
Output is correct |
5 |
Correct |
19 ms |
41356 KB |
Output is correct |
6 |
Correct |
19 ms |
41308 KB |
Output is correct |
7 |
Correct |
33 ms |
41564 KB |
Output is correct |
8 |
Correct |
32 ms |
41548 KB |
Output is correct |
9 |
Correct |
32 ms |
41500 KB |
Output is correct |
10 |
Correct |
31 ms |
41536 KB |
Output is correct |
11 |
Correct |
35 ms |
41584 KB |
Output is correct |
12 |
Correct |
29 ms |
41516 KB |
Output is correct |
13 |
Correct |
1223 ms |
53620 KB |
Output is correct |
14 |
Correct |
1221 ms |
53612 KB |
Output is correct |
15 |
Correct |
1164 ms |
53684 KB |
Output is correct |
16 |
Correct |
1190 ms |
53484 KB |
Output is correct |
17 |
Correct |
1174 ms |
53436 KB |
Output is correct |
18 |
Correct |
1227 ms |
54200 KB |
Output is correct |