oj.uz

Submission #677774

# Submission time Handle Problem Language Result Execution time Memory
677774 2023-01-04T10:57:37 Z bashkort Furniture (JOI20_furniture) C++17
100 / 100
 346 ms 22536 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1004, dx[]{0, 0, -1, 1}, dy[]{-1, 1, 0, 0};

int c[N][N], dead[N][N];

int fn[N + 7][N + 7];

void add(int i, int j) {
    for (int x = i + 1; x < N; x += x & -x) {
        for (int y = j + 1; y < N; y += y & -y) {
            fn[x][y] += 1;
        }
    }
}

int sum(int i, int j) {
    int ans = 0;
    for (int x = i + 1; x > 0; x -= x & -x) {
        for (int y = j + 1; y > 0; y -= y & -y) {
            ans += fn[x][y];
        }
    }
    return ans;
}

int rangeSum(int i1, int j1, int i2, int j2) {
    return sum(i2, j2) + sum(i1 - 1, j1 - 1) - sum(i2, j1 - 1) - sum(i1 - 1, j2);
}

bool full(int i1, int j1, int i2, int j2) {
    if (i1 > i2 || j1 > j2) return true;
    return (i2 - i1 + 1) * (j2 - j1 + 1) == rangeSum(i1, j1, i2, j2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    queue<pair<int, int>> consider;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c[i][j];

            if (c[i][j]) {
                consider.emplace(i, j);
            }
        }
    }
    for (int j = 2; j <= m + 1; ++j) {
        c[0][j] = 1;
        consider.emplace(0, j);
    }
    for (int i = 2; i <= n + 1; ++i) {
        c[i][0] = 1;
        consider.emplace(i, 0);
    }
    for (int j = 0; j <= m - 1; ++j) {
        c[n + 1][j] = 1;
        consider.emplace(n + 1, j);
    }
    for (int i = 0; i <= n - 1; ++i) {
        c[i][m + 1] = 1;
        consider.emplace(i, m + 1);
    }


    auto normalize = [&]() {
        while (!consider.empty()) {
            auto [i, j] = consider.front();
            consider.pop();

            if (dead[i][j]) {
                continue;
            }

            dead[i][j] = c[i][j];
            if (i && j && dead[i - 1][j] && dead[i][j - 1]) {
                dead[i][j] = 1;
            }
            if (dead[i][j + 1] && dead[i + 1][j]) {
                dead[i][j] = 1;
            }

            if (dead[i][j]) {
                for (int k = 0; k < size(dx); ++k) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni > 0 && nj > 0 && ni < n + 1 && nj < m + 1 && !dead[ni][nj]) {
                        consider.emplace(ni, nj);
                    }
                }
                add(i, j);
            }
        }
    };

    normalize();

    int q;
    cin >> q;

    while (q--) {
        int i, j;
        cin >> i >> j;

        if (dead[i][j]) {
            c[i][j] = 1;
            cout << "1\n";
            continue;
        }

        bool dont_need = false;
        if (!full(i + 1, 1, n, j - 1)) {
            dont_need = true;
        }

        if (!full(1, j + 1, i - 1, m)) {
            dont_need = true;
        }

        if (dont_need) {
            c[i][j] = 1;
            consider.emplace(i, j);

            normalize();

            cout << "1\n";
        } else {
            cout << "0\n";
        }

    }

    return 0;
}

Compilation message

furniture.cpp: In lambda function:
furniture.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 for (int k = 0; k < size(dx); ++k) {
      |                                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 3 ms 1500 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1620 KB Output is correct
6 Correct 4 ms 1620 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 4 ms 1620 KB Output is correct
9 Correct 4 ms 1596 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 3 ms 1500 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1620 KB Output is correct
6 Correct 4 ms 1620 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 4 ms 1620 KB Output is correct
9 Correct 4 ms 1596 KB Output is correct
10 Correct 12 ms 1620 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 253 ms 18364 KB Output is correct
13 Correct 99 ms 17000 KB Output is correct
14 Correct 338 ms 22536 KB Output is correct
15 Correct 346 ms 20980 KB Output is correct
16 Correct 287 ms 21300 KB Output is correct
17 Correct 318 ms 21968 KB Output is correct
18 Correct 323 ms 21492 KB Output is correct
19 Correct 337 ms 21940 KB Output is correct
20 Correct 263 ms 21852 KB Output is correct
21 Correct 325 ms 21892 KB Output is correct