Submission #166187

#	Time	Username	Problem	Language	Result	Execution time	Memory
166187		Eae02	Global Warming (CEOI18_glo)	C++14	100 / 100	399 ms	14940 KiB

glo

#include <bits/stdc++.h>
#define all(d) begin(d), end(d)
using namespace std;
using ll = long long;

struct SegTree {
	using T = ll;
	T f(T a, T b) { return max(a, b); }
	static constexpr T UNIT = 0;
	
	vector<T> s; ll n;
	SegTree(ll len) : s(2 * len, UNIT), n(len) {}
	void set(ll pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(ll lo, ll hi) { // query lo to hi (hi not included)
		T ra = UNIT, rb = UNIT;
		for (lo += n, hi += n; lo < hi; lo /= 2, hi /= 2) {
			if (lo % 2) ra = f(ra, s[lo++]);
			if (hi % 2) rb = f(s[--hi], rb);
		}
		return f(ra, rb);
	}
};

int main() {
	ll n, d;
	cin >> n >> d;
	
	vector<ll> a(n);
	for (ll i = 0; i < n; i++)
		cin >> a[i];
	
	vector<ll> distinctA = a;
	distinctA.push_back(LLONG_MIN);
	distinctA.push_back(LLONG_MAX);
	sort(all(distinctA));
	distinctA.erase(unique(all(distinctA)), distinctA.end());
	
	vector<array<ll, 2>> dp(n);
	
	ll ans = 0;
	vector<SegTree> st;
	st.emplace_back(distinctA.size());
	st.emplace_back(distinctA.size());
	for (ll i = n - 1; i >= 0; i--) {
		ll lo1 = upper_bound(all(distinctA), a[i]) - distinctA.begin();
		for (ll u = 0; u < 2; u++)
			dp[i][u] = st[u].query(lo1, distinctA.size()) + 1;
		
		ll lo2 = upper_bound(all(distinctA), a[i] - d) - distinctA.begin();
		dp[i][1] = max(dp[i][1], st[0].query(lo2, distinctA.size()) + 1);
		
		for (ll u = 0; u < 2; u++)
			st[u].set(lo1 - 1, dp[i][u]);
		
		ans = max(ans, dp[i][1]);
	}
	
	cout << ans << "\n";
}

• 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