Submission #1145022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145022		am_aadvik	Global Warming (CEOI18_glo)	C++20	75 / 100	72 ms	16116 KiB

glo

#include <iostream>
#include<vector>
#include<math.h>
#define int long long
using namespace std;

int lis(vector<int>a) {
	vector<vector<int>> arr = { {a[0]} };
	for (int i = 1; i < a.size(); ++i) {
		int s = 0, e = arr.size() - 1, res = arr.size();
		while (s <= e) {
			int mid = (s + e) / 2;
			if (arr[mid].back() < a[i])  s = mid + 1;
			else  e = mid - 1, res = mid;
		}
		if (res == arr.size()) arr.push_back({ a[i] });
		else arr[res].push_back(a[i]);
	}
	return (int)arr.size();
}
int32_t main() {
	int n, lm; cin >> n >> lm;
	vector<int> a(n);
	for (auto& x : a) cin >> x;
	if (n <= 1000) {
		int ans = 1;
		for (int l = 0; l < n; ++l) 
			a[l] -= lm, ans = max(ans, lis(a));
		cout << ans;
		return 0;
	}

	vector<vector<int>> arr = {};
	vector<int> idx(n);
	int ans = 1;
	for (int i = 0; i < a.size(); ++i) {
		int s = 0, e = arr.size() - 1, res = arr.size();
		while (s <= e) {
			int mid = (s + e) / 2;
			if (arr[mid].back() < (a[i] - lm))  s = mid + 1;
			else  e = mid - 1, res = mid;
		}
		idx[i] = res;
		if (res == arr.size()) arr.push_back({ (a[i] - lm) });
		else arr[res].push_back((a[i] - lm));
	}

	vector<vector<int>> arr2 = {};
	for (int i = a.size() - 1; i >= 0; --i) {
		int s = 0, e = arr2.size() - 1, res = -1;
		while (s <= e) {
			int mid = (s + e) / 2;
			if (arr2[mid].back() <= arr.back().back()) e = mid - 1;
			else res = mid, s = mid + 1;
		}
		ans = max(ans, res + (int)arr.size() + 1);

		arr[idx[i]].pop_back();
		if (arr[idx[i]].size() == 0) arr.pop_back();
		s = 0, e = arr2.size() - 1, res = arr2.size();
		while (s <= e) {
			int mid = (s + e) / 2;
			if (arr2[mid].back() > a[i])  s = mid + 1;
			else  e = mid - 1, res = mid;
		}
		if (res == arr2.size()) arr2.push_back({ a[i] });
		else arr2[res].push_back(a[i]);
	}
	cout << 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: 0 / 25