oj.uz

답안 #950795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950795 2024-03-20T17:32:01 Z amirhoseinfar1385 Sjeckanje (COCI21_sjeckanje) C++17
15 / 110
 2000 ms 35684 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);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	for(int i=0;i<q;i++){
		int l,r,w;
		cin>>l>>r>>w;
		for(int j=l;j<=r;j++){
			all[j]+=w;
		}
		vector<long long>dp(n+2);
		for(int j=1;j<=n;j++){
			long long mn=inf,mx=-inf;
			long long fmx=-inf,fmn=inf;
			dp[j]=-inf;
			for(int h=j;h>=1;h--){
				fmx=max(fmx,all[h]);
				fmn=min(fmn,all[h]);
				dp[j]=max(dp[j],dp[h-1]+fmx-fmn);
			}
			//res=max(res,mx-mn+max(fmx-fmn,0ll));
		}
		cout<<dp[n]<<"\n";
	}
	return 0;
	vorod();
	solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:157:14: warning: unused variable 'mn' [-Wunused-variable]
  157 |    long long mn=inf,mx=-inf;
      |              ^~
Main.cpp:157:21: warning: unused variable 'mx' [-Wunused-variable]
  157 |    long long mn=inf,mx=-inf;
      |                     ^~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 35516 KB Output is correct
2 Correct 12 ms 35420 KB Output is correct
3 Correct 13 ms 35508 KB Output is correct
4 Correct 14 ms 35684 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct
6 Correct 12 ms 35420 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 35516 KB Output is correct
2 Correct 12 ms 35420 KB Output is correct
3 Correct 13 ms 35508 KB Output is correct
4 Correct 14 ms 35684 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct
6 Correct 12 ms 35420 KB Output is correct
7 Execution timed out 2031 ms 35616 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 35516 KB Output is correct
2 Correct 12 ms 35420 KB Output is correct
3 Correct 13 ms 35508 KB Output is correct
4 Correct 14 ms 35684 KB Output is correct
5 Correct 12 ms 35420 KB Output is correct
6 Correct 12 ms 35420 KB Output is correct
7 Execution timed out 2031 ms 35616 KB Time limit exceeded
8 Halted 0 ms 0 KB -