제출 #1270628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270628		cmiuc	Global Warming (CEOI18_glo)	C++20	0 / 100	91 ms	4168 KiB

glo

#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) - 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] - 1) - 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;
}

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