제출 #1309015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309015		ppmn_6	Global Warming (CEOI18_glo)	C++20	62 / 100	38 ms	7252 KiB

glo

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n, x, ans = 0;
    cin >> n >> x;
    vector<ll> a(n);
    vector<pair<ll, ll>> op(n);
    vector<ll> dp1, dp2;
    for (ll i = 0; i < n - 1; i++) {
		cin >> a[i];
		auto it = lower_bound(dp1.begin(), dp1.end(), a[i]);
		if (it != dp1.end()) {
			op[i] = {it - dp1.begin(), *it};
			*it = a[i];
		}
		else {
			op[i] = {-1, -1};
			dp1.push_back(a[i]);
		}
	}
	cin >> a[n - 1];
	for (ll i = n - 1; i > 0; i--) {
		auto it = lower_bound(dp2.begin(), dp2.end(), -a[i]);
		if (it != dp2.end()) {
			*it = -a[i];
		}
		else {
			dp2.push_back(-a[i]);
		}
		ll res = lower_bound(dp1.begin(), dp1.end(), -(dp2.back() - x)) - dp1.begin();
		ans = max(ans, ll(res + dp2.size()));
		res = lower_bound(dp2.begin(), dp2.end(), -(dp1.back() - x)) - dp2.begin();
		ans = max(ans, ll(res + dp1.size()));
		if (op[i - 1].first == -1) {
			dp1.pop_back();
		}
		else {
			dp1[op[i - 1].first] = op[i - 1].second;
		}
	}
	cout << ans;
 
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25