oj.uz

Submission #561958

# Submission time Handle Problem Language Result Execution time Memory
561958 2022-05-13T23:52:09 Z 4fecta Furniture (JOI20_furniture) C++17
100 / 100
 296 ms 27728 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 1005;

int n, m, q, r, c, a[MN][MN], reach[MN][MN], cnt[MN + MN];

void block(int i, int j) {
    reach[i][j] = 0;
    cnt[i + j]--;
    if (!reach[i + 1][j - 1] && reach[i + 1][j]) block(i + 1, j);
    if (!reach[i + 1][j - 1] && reach[i][j - 1]) block(i, j - 1);
    if (!reach[i - 1][j + 1] && reach[i - 1][j]) block(i - 1, j);
    if (!reach[i - 1][j + 1] && reach[i][j + 1]) block(i, j + 1);
}

int32_t main() {
    boost();

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            reach[i][j] = 1;
            cnt[i + j]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] && reach[i][j]) block(i, j);
        }
    }
    cin >> q;
    while (q--) {
        cin >> r >> c;
        if (!reach[r][c]) printf("1\n");
        else if (cnt[r + c] == 1) printf("0\n");
        else printf("1\n"), block(r, c);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 2 ms 1364 KB Output is correct
5 Correct 3 ms 1352 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1364 KB Output is correct
8 Correct 3 ms 1368 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 2 ms 1364 KB Output is correct
5 Correct 3 ms 1352 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1364 KB Output is correct
8 Correct 3 ms 1368 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct
10 Correct 10 ms 1620 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 126 ms 20620 KB Output is correct
13 Correct 50 ms 17232 KB Output is correct
14 Correct 261 ms 24536 KB Output is correct
15 Correct 218 ms 24808 KB Output is correct
16 Correct 258 ms 26024 KB Output is correct
17 Correct 270 ms 27244 KB Output is correct
18 Correct 295 ms 26608 KB Output is correct
19 Correct 289 ms 27656 KB Output is correct
20 Correct 213 ms 27672 KB Output is correct
21 Correct 296 ms 27728 KB Output is correct