제출 #1213312

#제출 시각아이디문제언어결과실행 시간메모리
1213312shrek_loverGlobal Warming (CEOI18_glo)C++20
100 / 100
209 ms11348 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 

using namespace std;
using namespace __gnu_pbds;

typedef tree <int, null_type,  less<int>,  rb_tree_tag,  tree_order_statistics_node_update> ordered_set;

const int INF = 1e9 + 1000;
const int mxn = 1e6 + 100;
int dp[mxn], a[mxn], n, x;

int main() {
	cin >> n >> x;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int ans = 0;

	ordered_set suf;
	for(int i = n; i >= 1; i--) {
		dp[i] = suf.order_of_key(-a[i]) + 1;
		auto it = suf.lower_bound(-a[i]);
		if(it != suf.end()) suf.erase(it);
		suf.insert(-a[i]);
	}

	ordered_set pre;
	for(int i = 1; i <= n; i++) {
		int T = pre.order_of_key(a[i]);
		// cout << i << ": " << T << " + " << dp[i] << endl;
		// for(int x : pre)
		// 	cout << x << ' ';
		// cout << endl;
		ans = max(ans, T + dp[i]);
		auto it = pre.lower_bound(a[i] - x);
		if(it != pre.end()) pre.erase(it);
		pre.insert(a[i] - x);
	}

	cout << ans << endl;
	return 0;
}
#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...