Submission #1081982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081982		vuavisao	Global Warming (CEOI18_glo)	C++14	100 / 100	443 ms	19568 KiB

glo

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

const int N = (int) 2e5 + 10;

int n, x;
int a[N];

int b[4][N];

int n_node;
int tree[2][N * 4];

int prf[N][2];
int res;

void Update(int id, int idx, int val) {
	for( ; idx <= n_node; idx += (idx & - idx)) tree[id][idx] = max(tree[id][idx], val);
}

int Query(int id, int idx) {
	int res = 0;
	for( ; idx > 0; idx -= (idx & - idx)) res = max(res, tree[id][idx]);
	return res;
}

void reset(int id, int idx) {
	for ( ; idx <= n_node; idx += (idx & - idx)) tree[id][idx] = 0;
}

void compress() {
	vector<int> Pos = {};
	for (int i = 1; i <= n; ++ i) {
		Pos.push_back(b[0][i]);
		Pos.push_back(b[1][i]);
		Pos.push_back(b[2][i]);
		Pos.push_back(b[3][i]);
	}
	
	sort(Pos.begin(), Pos.end());
	Pos.resize(unique(Pos.begin(), Pos.end()) - Pos.begin());

	for (int i = 1; i <= n; ++ i) {
		b[0][i] = lower_bound(Pos.begin(), Pos.end(), b[0][i]) - Pos.begin() + 1;
		b[1][i] = lower_bound(Pos.begin(), Pos.end(), b[1][i]) - Pos.begin() + 1;
		b[2][i] = lower_bound(Pos.begin(), Pos.end(), b[2][i]) - Pos.begin() + 1;
		b[3][i] = lower_bound(Pos.begin(), Pos.end(), b[3][i]) - Pos.begin() + 1;
	}
}

void solve() {
	for (int i = 1; i <= n; ++ i) {
		b[0][i] = a[i];
		b[1][i] = a[i] - x;
		b[2][i] = -b[0][i];
		b[3][i] = -b[1][i];
	}
	compress();
	n_node = 4 * n;
	for (int i = 1; i <= n; ++ i) {
		int val[2] = {b[0][i], b[1][i]};
		prf[i][0] = Query(0, val[0]);
		Update(0, val[0] + 1, prf[i][0] + 1);

		prf[i][0] = max(prf[i][0], Query(1, val[0]));
		
		prf[i][1] = Query(1, val[1]);
		Update(1, val[1] + 1, prf[i][1] + 1);
	}
	for (int i = 1; i <= n; ++ i) {
		reset(0, b[0][i] + 1);
		reset(1, b[1][i] + 1);
	}

	for (int i = n; i >= 1; -- i) {
		int best[2] = {Query(0, b[2][i]), Query(0, b[3][i])};
		res = max(res, best[0] + prf[i][0] + 1);
		res = max(res, best[1] + prf[i][1] + 1);
		Update(0, b[2][i] + 1, best[0] + 1);
	}
	
	for (int i = 1; i <= n; ++ i) {
		reset(0, b[2][i] + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> x;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	solve();
	reverse(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++ i) a[i] = -a[i];
	solve();
	cout << res;
	return 0;
}

• 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