Submission #1213312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213312		shrek_lover	Global Warming (CEOI18_glo)	C++20	100 / 100	209 ms	11348 KiB

glo

#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;
}

• 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