제출 #679210

#제출 시각아이디문제언어결과실행 시간메모리
67921042kangarooGlobal Warming (CEOI18_glo)C++17
0 / 100
78 ms16304 KiB
//
// 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
 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...