Submission #1213308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213308		shrek_lover	Global Warming (CEOI18_glo)	C++20	0 / 100	183 ms	11360 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 x = pre.order_of_key(a[i]) + dp[i];
		ans = max(ans, x);
		pre.insert(a[i] - x);
	}

	cout << ans << 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