oj.uz

Submission #677771

# Submission time Handle Problem Language Result Execution time Memory
677771 2023-01-04T10:56:31 Z bashkort Furniture (JOI20_furniture) C++17
100 / 100
 430 ms 23760 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();

    auto print = [&]() {
        for (int i = 0; i <= n + 1; ++i) {
            for (int j = 0; j <= m + 1; ++j) {
                cout << dead[i][j];
            }
            cout << endl;
        }
        cout << endl;
    };

//    print();

    int q;
    cin >> q;

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

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

        int i1 = i + 1;
        int j1 = 1;
        int i2 = n;
        int j2 = j - 1;

        bool dont_need = false;
        if (!full(i1, j1, i2, j2)) {
            dont_need = true;
        }

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

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

            normalize();

//            cout << "added: " << i << " " << j << endl;
//            print();

            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) {
      |                                 ~~^~~~~~~~~~
furniture.cpp: In function 'int main()':
furniture.cpp:106:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  106 |     auto print = [&]() {
      |          ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 4 ms 1684 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 4 ms 1680 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 12 ms 1604 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 255 ms 18320 KB Output is correct
13 Correct 98 ms 16908 KB Output is correct
14 Correct 356 ms 22600 KB Output is correct
15 Correct 430 ms 21068 KB Output is correct
16 Correct 279 ms 22260 KB Output is correct
17 Correct 323 ms 23460 KB Output is correct
18 Correct 336 ms 22728 KB Output is correct
19 Correct 314 ms 23760 KB Output is correct
20 Correct 271 ms 23676 KB Output is correct
21 Correct 318 ms 23752 KB Output is correct