Submission #1314744

#TimeUsernameProblemLanguageResultExecution timeMemory
1314744qwertzGlobal Warming (CEOI18_glo)C++20
100 / 100
144 ms90140 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, x, ans;
	cin >> n >> x;
	vector<int> a(n), dp1;
	vector<stack<int>> dp2;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = n - 1; i >= 0; i--) {
		if (dp2.empty() || dp2.back().top() > a[i]) {
			dp2.push_back(stack<int>());
			dp2.back().push(a[i]);
			continue;
		}
		int l = -1, r = dp2.size() - 1;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			if (dp2[m].top() == a[i]) l = r = m;
			else if (dp2[m].top() < a[i]) r = m;
			else l = m;
		}
		dp2[r].push(a[i]);
	}
	ans = dp2.size();
	for (int i = 0; i < n; i++) {
		int l = 0, r = dp2.size() - 1;
		while (l != r) {
			int m = (l + r) / 2;
			if (dp2[m].top() == a[i]) l = r = m;
			else if (dp2[m].top() < a[i]) r = m - 1;
			else l = m + 1;
		}
		dp2[l].pop();
		if (dp2.back().empty()) dp2.pop_back();
		a[i] -= x;
		int len;
		if (dp1.empty() || a[i] > dp1.back()) {
			len = dp1.size();
			dp1.push_back(a[i]);
		}
		else {
			int p = lower_bound(dp1.begin(), dp1.end(), a[i]) - dp1.begin();
			dp1[p] = a[i];
			len = p;
		}
		if (dp2.empty() || dp2.back().top() > a[i]) len += dp2.size() + 1;
		else {
			l = -1, r = dp2.size() - 1;
			while (l + 1 < r) {
				int m = (l + r) / 2;
				if (dp2[m].top() == a[i]) l = r = m;
				else if (dp2[m].top() < a[i]) r = m;
				else l = m;
			}
			len += ++r;
		}
		ans = max(ans, len);
	}
	cout << ans;
	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...