Submission #99621

#	Time	Username	Problem	Language	Result	Execution time	Memory
99621		Anai	Global Warming (CEOI18_glo)	C++14	0 / 100	60 ms	4344 KiB

glo

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

using i64 = long long;

const int N = 2e5 + 5;

i64 v[N];
int dr[N];

vector<i64> stk;
i64 k;
int ant, n;


int main() {
#ifdef HOME
	freopen("glo.in", "r", stdin);
	freopen("glo.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

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

	if (n == 1) {
		cout << "1\n";
		return 0; }

	for (int i = n; i >= 1; --i) {
		auto it = lower_bound(begin(stk), end(stk), -v[i]);
		dr[i] = it - begin(stk) + 1;
		if (it == end(stk))
			stk.push_back(-v[i]);
		else
			*it = -v[i]; }

	stk.clear();
	for (int i = 1; i < n; ++i) {
		auto it = lower_bound(begin(stk), end(stk), v[i + 1]);
		dr[i] = it - begin(stk) + 1;
		if (it == end(stk))
			stk.push_back(v[i]);
		else
			*it = v[i];

		it = lower_bound(begin(stk), end(stk), v[i + 1] + k);
		ant = max(ant, dr[i + 1] + int(it - begin(stk))); }

	cout << ant << endl;

	return 0; }

• 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