Submission #94454

#	Time	Username	Problem	Language	Result	Execution time	Memory
94454		Noam527	Global Warming (CEOI18_glo)	C++17	100 / 100	81 ms	6524 KiB

glo

#include <bits/stdc++.h>
#include <unordered_set>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n, x;
vector<int> a;

vector<int> dp[2];
int L[2] = {};
vector<pair<int, int>> rev;

int upd(int ind, int val) {
	int lo, hi, mid;
	if (ind == 0) {
		lo = 0, hi = L[0] + 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (val <= dp[0][mid]) hi = mid;
			else lo = mid + 1;
		}
		rev.push_back({ lo, dp[0][lo] });
		dp[0][lo] = val;
		L[0] = max(L[0], lo);
	}
	else {
		lo = 0, hi = L[1] + 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (val >= dp[1][mid]) hi = mid;
			else lo = mid + 1;
		}
		dp[1][lo] = val;
		L[1] = max(L[1], lo);
	}
	return lo;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> x;
	a.resize(n);
	dp[0].resize(n + 1, 2 * inf), dp[1].resize(n + 1, -2 * inf);
	dp[0][0] = -2 * inf;
	dp[1][0] = 2 * inf;

	for (auto &i : a) cin >> i, upd(0, i);
	int ans = L[0];
	for (int i = n - 1, pos1, pos0; i >= 0; i--) {
		pos1 = upd(1, a[i]);
		pos0 = rev.back().first;
		dp[0][rev.back().first] = rev.back().second;
		if (rev.back().second == 2 * inf) L[0]--;
		rev.pop_back();

//		cout << "i " << i << '\n';
//		for (int j = 0; j <= L[0] + 1; j++) cout << dp[0][j] << " "; cout << '\n';
//		for (int j = 0; j <= L[1] + 1; j++) cout << dp[1][j] << " "; cout << '\n';

		int lo, hi, mid;
		lo = 0, hi = L[1];
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (dp[0][pos0] - x < dp[1][mid]) lo = mid;
			else hi = mid - 1;
		}
//		cout << "try 1: " << pos0 << " + " << lo << '\n';
		ans = max(ans, pos0 + lo);

		lo = 0, hi = L[0];
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (dp[1][pos1] + x > dp[0][mid]) lo = mid;
			else hi = mid - 1;
		}
//		cout << "try 2: " << pos1 << " + " << lo << '\n';
		ans = max(ans, pos1 + lo);
	}
	finish(ans);
}

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