Submission #824950

#	Time	Username	Problem	Language	Result	Execution time	Memory
824950		alex_2008	Global Warming (CEOI18_glo)	C++14	100 / 100	92 ms	6164 KiB

glo

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 2e5 + 10;
int a[N], dppref[N], dpsuff[N];
int main() {
	int n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int sz = 0;
	vector <int> lis(n + 1, 1e9 + 10);
	lis[0] = 0;
	for (int i = 1; i <= n; i++) {
		int ind = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
		if (a[i] > lis[ind - 1] && a[i] < lis[ind]) {
			lis[ind] = a[i];
			if (lis[ind + 1] == 1e9 + 10) sz = ind + 1;
		}
		dppref[i] = ind;
	}
	sz = 0;
	vector <int> lds(n + 1, -1e9);
	lds[n] = 1e9 + 10;
	for (int i = n; i >= 1; i--) {
		int ind = upper_bound(lds.begin(), lds.end(), a[i] - x) - lds.begin();
		dpsuff[i] = n + 1 - ind;
		ind = upper_bound(lds.begin(), lds.end(), a[i]) - lds.begin();
		if (a[i] < lds[ind] && a[i] > lds[ind - 1]) {
			lds[ind - 1] = a[i];
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dppref[i] + dpsuff[i] - 1);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:15:6: warning: variable 'sz' set but not used [-Wunused-but-set-variable]
   15 |  int sz = 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