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;
}