제출 #1309515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309515		comet0	Global Warming (CEOI18_glo)	C++20	100 / 100	135 ms	7508 KiB

glo

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

struct BIT {
	int n;
	vector<int> bit;
	BIT(int n=0): n(n), bit(n+1, 0) {}
	void reset(int n_) { n = n_; bit.assign(n+1, 0); }
	void update(int i, int val) {
		for (; i <= n; i += i & -i) bit[i] = max(bit[i], val);
	}
	int query(int i) const {
		int res = 0;
		for (; i > 0; i -= i & -i) res = max(res, bit[i]);
		return res;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	ll x;
	if (!(cin >> n >> x)) return 0;
	vector<ll> a(n);
	for (auto& v : a) cin >> v;

	vector<ll> b = a;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	int m = b.size();

	auto id = [&](ll v) {
		return int(lower_bound(b.begin(), b.end(), v) - b.begin()) + 1;
	};

	vector<int> l(n), r(n);
	BIT f(m);
	for (int i = 0; i < n; i++) {
		int p = id(a[i]);
		l[i] = f.query(p - 1) + 1;
		f.update(p, l[i]);
	}

	BIT g(m);
	for (int i = n - 1; i >= 0; i--) {
		int p = id(a[i]);
		int q = m - p + 1;
		r[i] = g.query(q - 1) + 1;
		g.update(q, r[i]);
	}

	int ans = 0;
	for (int v : l) ans = max(ans, v);

	BIT h(m);
	for (int j = 0; j < n; j++) {
		ll t = a[j] + x;
		int p = int(lower_bound(b.begin(), b.end(), t) - b.begin());
		int s = h.query(p);
		ans = max(ans, s + r[j]);
		h.update(id(a[j]), l[j]);
	}

	cout << ans;
}

• 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