Submission #1094059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094059	2024-09-28T11:16:56 Z	alexander707070	Global Warming (CEOI18_glo)	C++14	45 / 100	2000 ms	180432 KB

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

const int inf=1e9;

struct ST{
	struct node{
		int l,r,val;
	};

	node tree[30*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,int 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(int d){
	seg[0].init();
	seg[1].init();
	seg[2].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;
		dp[i][1]=max(seg[1].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[0].getmax(1,0,2*inf,0,a[i]+d-1)+1);
		dp[i][2]=max(seg[2].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[1].getmax(1,0,2*inf,0,a[i]-d-1)+1);

		seg[0].update(1,0,2*inf,a[i],dp[i][0]);
		seg[1].update(1,0,2*inf,a[i],dp[i][1]);
		seg[2].update(1,0,2*inf,a[i],dp[i][2]);

		res=max(res,max(dp[i][0],max(dp[i][1],dp[i][2])));
	}

	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];
	}

	if(n<=1000){
		unordered_set<int> w;
		w.insert(0);

		for(int i=1;i<=n;i++){
			for(int f=i+1;f<=n;f++){
				if(a[i]-a[f]+1>=-x and a[i]-a[f]+1<=x){
					w.insert(a[i]-a[f]+1);
				}

				if(a[i]-a[f]-1>=-x and a[i]-a[f]-1<=x){
					w.insert(a[i]-a[f]-1);
				}
			}
		}

		for(int i:w){
			ans=max(ans,solve(i));
		}

		cout<<ans<<"\n";
		return 0;
	}

	long long l=-x,r=x,lt,rt;
	while(l+20<r){
		lt=l+(r-l+1)/3;
		rt=r-(r-l+1)/3;

		int ls=solve(lt);
		int rs=solve(rt);

		if(ls>rs)l=lt;
		else if(rs>ls)r=rt;
		else{
			break;
		}
	}

	for(int d=l;d<=r;d++){
		ans=max(ans,solve(d));
	}

	cout<<ans<<"\n";

    return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6488 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6488 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	2 ms	6488 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	6 ms	6624 KB	Output is correct
15	Correct	2 ms	6492 KB	Output is correct
16	Correct	3 ms	6492 KB	Output is correct
17	Correct	1 ms	6492 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6488 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	2 ms	6488 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	6 ms	6624 KB	Output is correct
15	Correct	2 ms	6492 KB	Output is correct
16	Correct	3 ms	6492 KB	Output is correct
17	Correct	1 ms	6492 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct
19	Execution timed out	2057 ms	11116 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	489 ms	180432 KB	Output is correct
2	Correct	459 ms	180028 KB	Output is correct
3	Correct	479 ms	180048 KB	Output is correct
4	Correct	466 ms	180216 KB	Output is correct
5	Correct	257 ms	99668 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	903 ms	54304 KB	Output is correct
2	Correct	900 ms	54608 KB	Output is correct
3	Correct	899 ms	54356 KB	Output is correct
4	Correct	590 ms	30892 KB	Output is correct
5	Correct	1 ms	6488 KB	Output is correct
6	Correct	642 ms	10844 KB	Output is correct
7	Correct	747 ms	38672 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2074 ms	98648 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6488 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	2 ms	6488 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	6 ms	6624 KB	Output is correct
15	Correct	2 ms	6492 KB	Output is correct
16	Correct	3 ms	6492 KB	Output is correct
17	Correct	1 ms	6492 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct
19	Execution timed out	2057 ms	11116 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Submission #1094059

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 17.0

Subtask #7
0 / 25.0