oj.uz

Submission #950859

# Submission time Handle Problem Language Result Execution time Memory
950859 2024-03-20T19:51:12 Z amirhoseinfar1385 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1354 ms 46100 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,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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35520 KB Output is correct
2 Correct 7 ms 35532 KB Output is correct
3 Correct 10 ms 35420 KB Output is correct
4 Correct 8 ms 35420 KB Output is correct
5 Correct 9 ms 35576 KB Output is correct
6 Correct 8 ms 35428 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35520 KB Output is correct
2 Correct 7 ms 35532 KB Output is correct
3 Correct 10 ms 35420 KB Output is correct
4 Correct 8 ms 35420 KB Output is correct
5 Correct 9 ms 35576 KB Output is correct
6 Correct 8 ms 35428 KB Output is correct
7 Correct 21 ms 35420 KB Output is correct
8 Correct 29 ms 35420 KB Output is correct
9 Correct 21 ms 35420 KB Output is correct
10 Correct 24 ms 35584 KB Output is correct
11 Correct 20 ms 35420 KB Output is correct
12 Correct 23 ms 35420 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35520 KB Output is correct
2 Correct 7 ms 35532 KB Output is correct
3 Correct 10 ms 35420 KB Output is correct
4 Correct 8 ms 35420 KB Output is correct
5 Correct 9 ms 35576 KB Output is correct
6 Correct 8 ms 35428 KB Output is correct
7 Correct 21 ms 35420 KB Output is correct
8 Correct 29 ms 35420 KB Output is correct
9 Correct 21 ms 35420 KB Output is correct
10 Correct 24 ms 35584 KB Output is correct
11 Correct 20 ms 35420 KB Output is correct
12 Correct 23 ms 35420 KB Output is correct
13 Correct 1193 ms 45512 KB Output is correct
14 Correct 1273 ms 45552 KB Output is correct
15 Correct 1316 ms 45440 KB Output is correct
16 Correct 1324 ms 45340 KB Output is correct
17 Correct 1245 ms 45344 KB Output is correct
18 Correct 1354 ms 46100 KB Output is correct