oj.uz

답안 #950798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950798 2024-03-20T17:40:09 Z amirhoseinfar1385 Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 9 ms 35416 KB 
#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){
		//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(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)){
		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)||extreme(i-1)){
		seg.shart(i-1);
	}
	if(extreme(i)||extreme(i+1)){
		seg.shart(i);
	}
}

void upd(long long l,long long r,long long w){
	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;
	//	//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();
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -