oj.uz

답안 #893160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893160 2023-12-26T15:18:28 Z Alcabel Furniture (JOI20_furniture) C++17
100 / 100
 249 ms 24860 KB 
#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>> bad;
    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)) {
                    bad.emplace_back(i, j);
                } else if (degIn[i][j] == 0 && (i != 0 || j != 0)) {
                    bad.emplace_back(i, j);
                }
                fen.add(i + 1, j + 1, 1);
            }
        }
    }
    // cerr << "!\n";
    auto erase = [&](int i, int j) -> void {
        assert(i != 0 || j != 0 || i != n - 1 || j != m - 1);
        if (a[i][j] == '1') {
            return;
        }
        a[i][j] = '1';
        degIn[i][j] = degOut[i][j] = 0;
        fen.add(i + 1, j + 1, -1);
        if (i + 1 < n && a[i + 1][j] == '0') {
            if (--degIn[i + 1][j] == 0) {
                bad.emplace_back(i + 1, j);
            }
        }
        if (j + 1 < m && a[i][j + 1] == '0') {
            if (--degIn[i][j + 1] == 0) {
                bad.emplace_back(i, j + 1);
            }
        }
        if (i - 1 >= 0 && a[i - 1][j] == '0') {
            if (--degOut[i - 1][j] == 0) {
                bad.emplace_back(i - 1, j);
            }
        }
        if (j - 1 >= 0 && a[i][j - 1] == '0') {
            if (--degOut[i][j - 1] == 0) {
                bad.emplace_back(i, j - 1);
            }
        }
    };
    auto purify = [&]() -> void {
        while (!bad.empty()) {
            auto [i, j] = bad.back();
            bad.pop_back();
            // cerr << i << ' ' << j << '\n';
            erase(i, j);
        }
    };
    auto print = [&]() -> void {
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < m; ++c) {
                cerr << a[r][c] << ' ';
            }
            cerr << '\n';
        }
        cerr << "---\n";
    };
    purify();
    // print();
    // 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';
        // print();
    }
}

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

Compilation message

furniture.cpp: In function 'void solve()':
furniture.cpp:111:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  111 |     auto print = [&]() -> void {
      |          ^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 8 ms 1372 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 161 ms 17236 KB Output is correct
13 Correct 64 ms 13812 KB Output is correct
14 Correct 226 ms 21584 KB Output is correct
15 Correct 225 ms 21076 KB Output is correct
16 Correct 201 ms 22752 KB Output is correct
17 Correct 216 ms 23892 KB Output is correct
18 Correct 249 ms 23380 KB Output is correct
19 Correct 244 ms 24688 KB Output is correct
20 Correct 212 ms 24860 KB Output is correct
21 Correct 229 ms 24660 KB Output is correct