Submission #679210

#	Time	Username	Problem	Language	Result	Execution time	Memory
679210		42kangaroo	Global Warming (CEOI18_glo)	C++17	0 / 100	78 ms	16304 KiB

glo

//
// Created by 42kangaroo on 07/01/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

struct Change {
	int pos, l;
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (auto &v: a) {
		cin >> v;
	}
	vector<int> dp(n, numeric_limits<int>::max());
	vector<Change> ch(n);
	for (int i = 0; i < n; ++i) {
		auto chP = std::upper_bound(dp.begin(), dp.end(), a[i]);
		ch[i] = {chP - dp.begin(), *chP};
		*chP = a[i];
	}
	int lis = std::lower_bound(dp.begin(), dp.end(), numeric_limits<int>::max())- dp.begin() + 1;
	int ma = 0;
	vector<int> dpD(n, numeric_limits<int>::min());
	for (int i = n - 1; i >= 0; --i) {
		auto chD = std::upper_bound(dpD.begin(), dpD.end(), a[i] + x, greater<>());
		dp[ch[i].pos] = ch[i].l;
		*chD = a[i] + x;
		ma = max(ma,
		         (chD - dpD.begin()) + n - (std::upper_bound(dp.rbegin(), dp.rend(), *chD, greater<>()) - dp.rbegin()) + 1);
		ma = max(ma, ch[i].pos + n - (std::upper_bound(dpD.rbegin(), dpD.rend(), ch[i].l) - dpD.rbegin()) + 1);

	}
	assert(x > 0 || lis == ma);
	cout << ma << "\n";
}/*
8 0
7 3 5 12 2 7 3 4
 */

• 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