Một bài toán có dạng 1000 hình chữ nhật trên lưới ô vuông 10⁹ x 10⁹

Cách giải đối với dạng bài này là nén lưới ô vuông 10⁹ x 10⁹ về lưới ô vuông 2N x 2N (N: 1..1000). Lời khuyên cho dạng bài này là: trên lưới ban đầu, dùng định nghĩa điểm thay vì ô. Trên lưới sau khi nén, dùng định nghĩa ô thay vì điểm.

Đề bài

Có N bức tường (N: 0..1000) có dạng hình chữ nhật nằm trên lưới ô vuông P x Q ô (P, Q: 1..10⁶). Một con rô bốt ở ô (x, y) có thể đi đến ô (x+1, y) và (x, y+1) miễn là ô nguồn và ô đích không có tường. Đếm số ô (x, y) không phải tường và rô bốt tại (x, y) không thể đi đến ô (P, Q).

Độ phức tạp

O(N²)

Code này của Nguyễn Tiến Trung Kiên

#include <bits/stdc++.h>

using namespace std;

#define long long long

#define all(a) a.begin(), a.end()

struct separator_list {

    vector<int> a;

    void insert(int x)

        { a.push_back(x); }

    void ready()

        { sort(all(a)); a.erase(unique(all(a)), a.end()); }

    int index(int x)

        { return lower_bound(all(a), x) - a.begin(); }

} xs, ys; //

struct worker {

    static const int N = 3003;

    int m, n, a[N][N];

    bool F[N][N];

    void init(int _m, int _n)

        { m=_m; n=_n; }

    void done() {

        for (int i=0; i<=m+1; i++)

        for (int j=0; j<=n+1; j++) {

            a[i][j] = 0;

            F[i][j] = false;

        }

    }

    void fill(int x, int y, int u, int v) {

        u++; v++;

        a[x][y]++; a[x][v]--;

        a[u][y]--; a[u][v]++;

    }

    void ready() {

        for (int i=1; i<=m; i++)

        for (int j=1; j<=n; j++)

        a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];

    }

    long solve(const vector<int> &xs, const vector<int> &ys) {

        for (int i=m; i>=1; i--)

        for (int j=n; j>=1; j--)

        if (a[i][j])

            F[i][j] = false;

        else if (i==m && j==n)

            F[i][j] = true;

        else

            F[i][j] = i<m && F[i+1][j] || j<n && F[i][j+1];

        long v0 = 0;

        for (int i=1; i<=m; i++)

        for (int j=1; j<=n; j++)

            if (!a[i][j] && !F[i][j])

            v0 += 1LL * (xs[i]-xs[i-1]) * (ys[j] - ys[j-1]);

        return v0;

    }

} W; //

const int N = 1003;

int xh, yh, n;

tuple<int, int, int, int> Rect[N];

void solve(int t) {

    scanf("%d%d%d", &yh, &xh, &n);

    if (xh==0 && yh==0 && n==0) exit(0);

    xs.insert(0); xs.insert(xh);

    ys.insert(0); ys.insert(yh);

    for (int i=1; i<=n; i++) {

        int x, y; scanf("%d%d", &x, &y);

        int u, v; scanf("%d%d", &u, &v); u++; v++;

        Rect[i] = make_tuple(x, y, u, v);

        xs.insert(x); ys.insert(y);

        xs.insert(u); ys.insert(v);

    }

    xs.ready(); ys.ready();

    W.init(xs.index(xh), ys.index(yh));

    for (int i=1; i<=n; i++) {

        int x, y, u, v; tie(x, y, u, v) = Rect[i];

        W.fill(xs.index(x+1), ys.index(y+1), xs.index(u), ys.index(v));

    }

    W.ready();

    printf("Case %d: %lld\n", t, W.solve(xs.a, ys.a));

}

int main() {

    for (int i=1; true; i++) {

        solve(i);

        xs.a.clear();

        ys.a.clear();

        W.done();

    }

}

Nhận xét

Bài này đã được dùng để nộp cho một bài trên UVa.

Tham khảo

https://uva.onlinejudge.org/external/10/1092.pdf