Submission #1273861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273861		crispxx	Global Warming (CEOI18_glo)	C++20	100 / 100	103 ms	9840 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

struct fenw {
	int n; vector<int> bit;
	
	fenw(int n) : n(n), bit(n + 1) {}
	
	void update(int i, int x) {
		for(; i <= n; i += i & -i) chmax(bit[i], x);
	}
	
	int get(int i) {
		int res = 0;
		for(; i >= 1; i -= i & -i) chmax(res, bit[i]);
		return res;
	}
};

const int inf = 1e18;

void solve() {
	int n, x; cin >> n >> x;
	
	vector<int> a(n);
	
	for(auto &x : a) cin >> x;
	
	auto b = a;
	sort(all(b));
	b.erase(unique(all(b)), b.end());
	
	int sz = b.size() + 1;
	
	vector<int> pref(n), suf(n);
	
	vector<int> dp(n + 1, inf);
	dp[0] = -inf;
	
	for(int i = 0; i < n; i++) {
		int j = lower_bound(all(dp), a[i]) - dp.begin();
		dp[j] = a[i];
		pref[i] = j;
	}
	
	for(int i = 0; i <= n; i++) dp[i] = inf;
	dp[0] = -inf;
	
	int ans = *max_element(all(pref));
	
	fenw fn(sz);
	
	for(int i = n - 1; i >= 0; i--) {
		int j = lower_bound(all(dp), -a[i]) - dp.begin();
		dp[j] = -a[i];
		
		chmax( ans, fn.get( sz - (upper_bound(all(b), a[i] - x) - b.begin()) ) + pref[i] );
		
		fn.update( sz - (lower_bound(all(b), a[i]) - b.begin()), j );

	}
	
	cout << ans << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• 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