Submission #893123

#	Time	Username	Problem	Language	Result	Execution time	Memory
893123		Alcabel	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	348 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n, m;
    vector<vector<int>> fen;
    Fenwick() {}
    Fenwick(int _n, int _m) {
        n = _n, m = _m;
        fen.resize(n + 1, vector<int>(m + 1));
    }
    void add(int i, int j, int x) {
        for (int row = i; row <= n; row += (row & -row)) {
            for (int col = j; col <= m; col += (col & -col)) {
                // cerr << row << ' ' << col << '\n';
                fen[row][col] += x;
            }
        }
    }
    int getPref(int i, int j) {
        int res = 0;
        for (int row = i; row > 0; row -= (row & -row)) {
            for (int col = j; col > 0; col -= (col & -col)) {
                res += fen[row][col];
            }
        }
        return res;
    }
    int getSum(int li, int lj, int ri, int rj) {
        return getPref(ri, rj) - getPref(li - 1, rj) - getPref(ri, lj - 1) + getPref(li - 1, lj - 1);
    }
    ~Fenwick() {}
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> degIn(n, vector<int>(m, -1)), degOut(n, vector<int>(m, -1));
    vector<pair<int, int>> badOut, badIn;
    Fenwick fen(n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '0') {
                degOut[i][j] = 0;
                if (i + 1 < n && a[i + 1][j] == '0') {
                    ++degOut[i][j];
                }
                if (j + 1 < m && a[i][j + 1] == '0') {
                    ++degOut[i][j];
                }
                degIn[i][j] = 0;
                if (i - 1 >= 0 && a[i - 1][j] == '0') {
                    ++degIn[i][j];
                }
                if (j - 1 >= 0 && a[i][j - 1] == '0') {
                    ++degIn[i][j];
                }
                if (degOut[i][j] == 0 && (i != n - 1 || j != m - 1)) {
                    badOut.emplace_back(i, j);
                }
                if (degIn[i][j] == 0 && (i != 0 || j != 0)) {
                    badIn.emplace_back(i, j);
                }
                fen.add(i + 1, j + 1, 1);
            }
        }
    }
    // cerr << "!\n";
    auto erase = [&](int i, int j) -> void {
        if (a[i][j] == '1') {
            return;
        }
        a[i][j] = '1';
        fen.add(i + 1, j + 1, -1);
        if (i + 1 < n && a[i + 1][j] == '0') {
            if (--degIn[i + 1][j] == 0) {
                badIn.emplace_back(i, j);
            }
        }
        if (j + 1 < m && a[i][j + 1] == '0') {
            if (--degIn[i][j + 1] == 0) {
                badIn.emplace_back(i, j);
            }
        }
        if (i - 1 >= 0 && a[i - 1][j] == '0') {
            if (--degOut[i - 1][j] == 0) {
                badOut.emplace_back(i - 1, j);
            }
        }
        if (j - 1 >= 0 && a[i][j - 1] == '0') {
            if (--degOut[i][j - 1] == 0) {
                badOut.emplace_back(i, j - 1);
            }
        }
    };
    auto purify = [&]() -> void {
        while (!badOut.empty() || !badIn.empty()) {
            if (!badOut.empty()) {
                auto [i, j] = badOut.back();
                badOut.pop_back();
                // cerr << i << ' ' << j << '\n';
                erase(i, j);
            } else {
                auto [i, j] = badIn.back();
                badIn.pop_back();
                // cerr << i << ' ' << j << '\n';
                erase(i, j);
            }
        }
    };
    purify();
    // cerr << "!!\n";
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        if (a[i - 1][j - 1] == '0' && fen.getSum(i + 1, 1, n, j - 1) + fen.getSum(1, j + 1, i - 1, m) > 0) {
            // cerr << "!\n";
            erase(i - 1, j - 1);
            purify();
        }
        cout << a[i - 1][j - 1] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95