제출 #1270630

#제출 시각아이디문제언어결과실행 시간메모리
1270630cmiucGlobal Warming (CEOI18_glo)C++20
100 / 100
88 ms4168 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
int a[N], dp1[N], dp2[N], ind[N], rep[N];

int solve(int n, int d, int Ans = 0){
	for (int i=0;i<=n;i++)
		dp1[i] = 2.1e9, dp2[i] = -dp1[i];
	dp1[0] = dp2[1];
	
	for (int i=1;i<=n;i++){
		int cur = a[i] - d;
		int u = upper_bound(dp1, dp1 + n + 1, cur - 1) - dp1;
		ind[i] = u, rep[i] = dp1[u];
		dp1[u] = cur;
		Ans = max(Ans, u);
	}

	for (int i=n;i>=1;i--){
		int u = upper_bound(dp2, dp2 + n + 1, a[i]) - dp2 - 1;
		dp2[u] = a[i];
		dp1[ind[i]] = rep[i];
		int u2 = upper_bound(dp1, dp1 + n + 1, a[i] - 1) - dp1;
		Ans = max(Ans, n - u + u2);
	}
	return Ans;
}

int main(){
	int n, x;
	cin>>n>>x;

	for (int i=1;i<=n;i++)
		cin>>a[i];

	cout<<solve(n, x)<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...