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

Download