Submission #950859

#	Time	Username	Problem	Language	Result	Execution time	Memory
950859		amirhoseinfar1385	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1354 ms	46100 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long all[maxn],n,q,kaf=(1<<19),inf=1e17;
struct node{
	long long res00,res01,res10,res11;
	node(){
		res00=res01=res10=res11=0;
	}
}fakenode;
struct fenwick{
	long long fn[maxn];
	fenwick(){
		for(long long i=0;i<maxn;i++){
			fn[i]=0;
		}
	}
	void upd(long long i,long long w){
	//	//cout<<i<<" "<<w<<" upd"<<endl;
		i++;
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	long long pors(long long i){
	//	//cout<<i<<" ";
		i++;
		long long ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
	//	//cout<<ret<<" pors:"<<endl;
		return ret;
	}
}fen;
struct segment{
	node seg[(1<<20)];
	node merge(node a,node b){
		node ret;
		ret.res00=max(a.res01+b.res00,max(a.res00+b.res10,a.res00+b.res00));
		ret.res10=max(a.res11+b.res00,max(a.res10+b.res10,a.res10+b.res00));
		ret.res01=max(a.res01+b.res01,max(a.res00+b.res11,a.res00+b.res01));
		ret.res11=max(a.res11+b.res01,max(a.res10+b.res11,a.res10+b.res01));
		return ret;
	}
	void ins(long long i,long long w){
		//cout<<"ins: "<<i<<" "<<w<<"\n"; 
		i+=kaf;
		seg[i].res00=seg[i].res10=seg[i].res01=seg[i].res11=w;
		i>>=1;
		while(i>0){
			seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
			i>>=1;
		}
	}
	void shart(long long i,long long w){
		//cout<<"shart: "<<i<<" "<<w<<"\n";
		i+=kaf;
		if(w==1){
			seg[i].res00=seg[i].res10=0;
		}else{
			seg[i].res00=seg[i].res01=0;
		}
		//seg[i].res00=seg[i].res10=seg[i].res01=0;
		i>>=1;
		while(i>0){
			seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
			i>>=1;
		}
	}
}seg;

void vorod(){
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
}

long long vas(long long l,long long r){
//	////cout<<l<<" "<<r<<" "<<fen.pors(l)<<" "<<fen.pors(r)<<"\n";
	if(l<=0||l>n||r<=0||r>n){
		assert(0);
	}
	if(fen.pors(l)<fen.pors(r)){
		return -1;
	}
	if(fen.pors(l)==fen.pors(r)){
		return 0;
	}
	return 1;
}

bool extreme(long long i){
	if(i<=1||i>=n){
		return 0;
	}
	if(vas(i-1,i)*vas(i+1,i)==1){
		return 1;
	}
	return 0;
}

void ins(long long i){
	if(i<1||i>n){
		return ;
	}
	if(i>1){
		seg.ins(i-1,abs(fen.pors(i)-fen.pors(i-1)));
	}if(i<n){
		seg.ins(i,abs(fen.pors(i+1)-fen.pors(i)));
	}
	if(extreme(i)){
		seg.shart(i-1,1);
	}
	if(extreme(i-1)){
		seg.shart(i-1,2);
	}
	if(extreme(i+1)){
		seg.shart(i,1);
	}
	if(extreme(i)){
		seg.shart(i,2);
	}
}

void upd(long long l,long long r,long long w){
	////cout<<l<<" "<<r<<" "<<w<<endl;
	fen.upd(l,w);
	fen.upd(r+1,-w);
	ins(l);
	ins(l-1);
	ins(r);
	ins(r+1);
}

void solve(){
	for(long long i=1;i<=n;i++){
		upd(i,i,all[i]);
	}
	for(long long i=0;i<q;i++){
		long long l,r,w;
		cin>>l>>r>>w;
		upd(l,r,w);
		cout<<max(max(seg.seg[1].res00,seg.seg[1].res01),max(seg.seg[1].res10,seg.seg[1].res11))<<"\n";
	}	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//////cout.tie(0);
//	freopen("inp.txt","r",stdin);
//	freopen("kharab.txt","w",stdout);
	vorod();
	solve();
//	for(int i=1;i<=n;i++){
//		cout<<seg.seg[i+kaf].res00<<" "<<seg.seg[i+kaf].res01<<" "<<seg.seg[i+kaf].res10<<" "<<seg.seg[i+kaf].res11<<" "<<i<<endl;
//	}
}

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