답안 #950762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950762 2024-03-20T16:15:18 Z amirhoseinfar1385 Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
7 ms 35672 KB
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int all[maxn],n,q,kaf=(1<<19);
struct node{
	long long res00,res01,res10,res11;
	node(){
		res00=res01=res10=res11=0;
	}
}fakenode;
struct fenwick{
	long long fn[maxn];
	fenwick(){
		for(int i=0;i<maxn;i++){
			fn[i]=0;
		}
	}
	void upd(int i,int w){
	//	//cout<<i<<" "<<w<<" upd"<<endl;
		i++;
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int 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(int i,int 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(int i){
		//cout<<"shart: "<<i<<"\n";
		i+=kaf;
		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(int i=1;i<=n;i++){
		cin>>all[i];
	}
}

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

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

void ins(int 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)||extreme(i-1)){
		seg.shart(i-1);
	}
	if(extreme(i)||extreme(i+1)){
		seg.shart(i);
	}
}

void upd(int l,int r,int w){
	fen.upd(l,w);
	fen.upd(r+1,-w);
	ins(l);
	ins(l-1);
	ins(r);
	ins(r+1);
}

void solve(){
	for(int i=1;i<=n;i++){
		upd(i,i,all[i]);
	}
	for(int i=0;i<q;i++){
		int l,r,w;
		cin>>l>>r>>w;
	//	//cout<<"wtf: "<<l<<" "<<r<<" "<<w<<endl;
		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);
	vorod();
	solve();
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 35672 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 35672 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 35672 KB Output isn't correct
2 Halted 0 ms 0 KB -