GOLD - Đảo giấu vàng

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<algorithm>
#include<iostream>
using namespace std;

const int X = 1e5, ABS = 3e4, LOG_X = 16, ST_SIZE = 1 << (LOG_X + 2), N = 15000;
int tree[ST_SIZE], common[ST_SIZE];
pair<int, int> gold[N];
int n, s, w;

void enter() {
	cin >> s >> w >> n;
	for(int i = 0; i < n; ++i) {
		cin >> gold[i].first >> gold[i].second;
		gold[i].second += ABS;
	}
}

void update(int k, int l, int r, int x, int y, int delta) {
	if(r <= x || r <= l || y <= l) return;
	if(x <= l && r <= y)
		tree[k] += delta, common[k] += delta;
	else {
		update(2 * k + 1, l, (l + r) / 2, x, y, delta);
		update(2 * k + 2, (l + r) / 2, r, x, y, delta);
		tree[k] = max(tree[2 * k + 1], tree[2 * k + 2]) + common[k];
	}
}

void solve() {
	sort(gold, gold + n);
	int res = 0;
	for(int l = 0, r = 0; r < n; ++r) {
		while(gold[l].first + s < gold[r].first)
			update(0, 0, X, gold[l].second, gold[l].second + w + 1, -1), ++l;
		update(0, 0, X, gold[r].second, gold[r].second + w + 1, 1);
		res = max(res, tree[0]);
	}
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	solve();
	return 0;
}

Download