GOLD - Đảo giấu vàng
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 60006;
const int OFFSET = 30001;
struct Node {
int l, r;
int lazy, maxV;
Node *left, *right;
Node(int l, int r): l(l), r(r), lazy(0), maxV(0), left(NULL), right(NULL) {}
void pushDown() {
if (lazy) {
maxV += lazy;
if (l < r) {
left->lazy += lazy;
right->lazy += lazy;
}
lazy = 0;
}
}
void gather() {
maxV = max(left->maxV, right->maxV);
}
void update(int i, int j, int v) {
pushDown();
if (r < i || j < l) return;
if (i <= l && r <= j) {
lazy += v;
pushDown();
return;
}
left->update(i, j, v);
right->update(i, j, v);
gather();
}
};
Node* build(int l, int r) {
Node *x = new Node(l, r);
if (l == r) return x;
x->left = build(l, l + r >> 1);
x->right = build((l + r >> 1) + 1, r);
return x;
}
Node *root;
vector<int> Y[SIZE];
int n, S, W;
void update(int x, int v) {
for (int i = 0; i < Y[x].size(); ++i) {
int y = Y[x][i];
root->update(y, y + W, v);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> S >> W;
cin >> n;
for (int i = 0; i < n; ++i) {
int x, y; cin >> x >> y;
x += OFFSET; y += OFFSET;
Y[x].push_back(y);
}
root = build(0, SIZE - 1);
int ans = 0;
for (int i = 0; i < SIZE; ++i) {
update(i, 1);
ans = max(ans, root->maxV);
if (i >= S) update(i - S, -1);
}
cout << ans << endl;
return 0;
}