Submission #1224835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224835		radodododo	Global Warming (CEOI18_glo)	C++20	27 / 100	776 ms	97476 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

struct segtree {
	vector<long long> tree;
	long long get_max(long long i, long long l, long long r, long long ql, long long qr) {
		if (qr <= l || r <= ql) {
			return 0;
		}
		if (ql <= l && r <= qr) {
			return tree[i];
		}
		long long mid = (l + r) / 2;
		return max(get_max(2 * i + 1, l, mid, ql, qr), get_max(2 * i + 2, mid, r, ql, qr));
	}
	void sett(long long i, long long l, long long r, long long qi, long long qx) {
		tree[i] = max(tree[i], qx);
		if (l + 1 == r) {
			return;
		}
		long long mid = (l + r) / 2;
		if (qi < mid) {
			sett(2 * i + 1, l, mid, qi, qx);
		} else {
			sett(2 * i + 2, mid, r, qi, qx);
		}
	}
};

int main() {
	long long n, x;
	cin >> n >> x;
	vector<long long> v(n);
	set<long long> s;
	for (long long i = 0; i < n; i++) {
		cin >> v[i];
		s.insert(v[i]);
		s.insert(v[i] + x);
	}
	map<long long, long long> nz, lz;
	long long cnt = 0;
	for (auto ch : s) {
		nz[ch] = cnt;
		lz[cnt] = ch;
		cnt++;
	}
	segtree tr1, tr2;
	tr1.tree.resize(4 * cnt);
	tr2.tree.resize(4 * cnt);
	vector<long long> dp(n);
	for (long long i = 0; i < n; i++) {
		long long ch = nz[v[i]];
		dp[i] = max(dp[i], tr1.get_max(0, 0, cnt, 0, ch) + 1);
		tr1.sett(0, 0, cnt, ch, dp[i]);
		tr2.sett(0, 0, cnt, ch, dp[i]);
		ch = nz[v[i] + x];
		long long newzn = tr2.get_max(0, 0, cnt, 0, ch) + 1;
		tr2.sett(0, 0, cnt, ch, newzn);
	}
	cout << max(tr1.get_max(0, 0, cnt, 0, cnt), tr2.get_max(0, 0, cnt, 0, cnt));
}

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