Submission #535655

#	Time	Username	Problem	Language	Result	Execution time	Memory
535655		new_acc	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1227 ms	54200 KiB

Main

#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();
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55