제출 #1094109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094109		alexander707070	Global Warming (CEOI18_glo)	C++14	100 / 100	298 ms	122020 KiB

glo

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
 
const long long inf=1e9;
 
struct ST{
	struct node{
		int l,r,val;
	};
 
	node tree[100*MAXN];
	int num;
	
	void init(){
		num=1;
		tree[num]={0,0,0};
	}
 
	void addnode(){
		num++;
		tree[num]={0,0,0};
	}
 
	void check(int v){
		if(tree[v].l==0){
			addnode(); tree[v].l=num;
		}
 
		if(tree[v].r==0){
			addnode(); tree[v].r=num;
		}
	}
 
	void update(int v,long long l,long long r,long long pos,int val){
		if(l==r){
			tree[v].val=max(tree[v].val,val);
		}else{
			long long tt=(l+r)/2;
			check(v);
 
			if(pos<=tt)update(tree[v].l,l,tt,pos,val);
			else update(tree[v].r,tt+1,r,pos,val);
 
			tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val);
		}
	}
 
	int getmax(int v,long long l,long long r,long long ll,long long rr){
		if(ll>rr or v==0)return 0;
		if(l==ll and r==rr){
			return tree[v].val;
		}else{
			long long tt=(l+r)/2;
			return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
		}
	}
}seg[3];
 
int n,a[MAXN],ans,x;
int dp[MAXN][3];
 
int solve(){
	seg[0].init();
	seg[1].init();

	int res=0;
	for(int i=1;i<=n;i++){
		dp[i][0]=seg[0].getmax(1,0,2*inf,0,a[i]-1)+1;
		seg[0].update(1,0,2*inf,a[i],dp[i][0]);
	}

	for(int i=n;i>=1;i--){
		dp[i][1]=seg[1].getmax(1,0,2*inf,a[i]+1,2*inf)+1;
		seg[1].update(1,0,2*inf,a[i],dp[i][1]);

		res=max(res,dp[i-1][0]+seg[1].getmax(1,0,2*inf,a[i-1]-x+1,2*inf));
	}

	return res;
}
 
int main(){
 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=inf;
	}
 
	cout<<solve()<<"\n";
 
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25