Submission #790935

#	Time	Username	Problem	Language	Result	Execution time	Memory
790935		acatmeowmeow	Global Warming (CEOI18_glo)	C++11	48 / 100	566 ms	262144 KiB

glo

#include <bits/stdc++.h>

using namespace std;

//#define int long long 

const int N = 2e5;
int n, x, arr[N + 5];

struct node {
	int v = 0;
	node *lef = nullptr, *rig = nullptr;

	void extend() {
		if (!lef) lef = new node(), rig = new node();
	}

	void update(long  long tl, long long tr, int k, int x) {
		if (tl == tr) v = max(v, x);
		else {
			extend();
			long long tm = tl + (tr - tl)/2;
			if (k <= tm) lef->update(tl, tm, k, x);
			else rig->update(tm + 1, tr, k, x);
			v = max(lef->v, rig->v);
		}
	}

	int query(long long tl, long long tr, long long l, long long r) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return v;
		else {
			extend();
			long long tm = tl + (tr - tl)/2;
			return max(lef->query(tl, tm, l, min(tm, r)), rig->query(tm + 1, tr, max(l, tm + 1), r));
		}
	}
} *root0 = new node(), *root1 = new node();

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> x;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int res0 = root0->query(-1e9, 2e9, -1e9, arr[i] - 1) + 1;
		int res1 = max(root1->query(-1e9, 2e9, -1e9, arr[i] - 1) + 1, root0->query(-1e9, 2e9, -1e9, arr[i] + x - 1) + 1);
		root0->update(-1e9, 2e9, arr[i], res0);
		root1->update(-1e9, 2e9, arr[i], res1);
		ans = max({ans, res0, res1});
	}
	cout << ans << '\n';
	return 0;
}

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