oj.uz

Submission #715669

# Submission time Handle Problem Language Result Execution time Memory
715669 2023-03-27T13:07:20 Z ParsaS Furniture (JOI20_furniture) C++17
100 / 100
 371 ms 5452 KB 
// In the name of God
//        : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1000 + 5;
bool di[2] = {0, 1}, dj[2] = {1, 0};
int n, m;
bool grid[N][N], ok[2][N][N];
int cnt[N * 2];

bool valid(int i, int j) {
    return i >= 0 && j >= 0 && i < n && j < m && grid[i][j] == 0;
}

void dfs(int s, int t, int k) {
    ok[k == -1][s][t] = true;
    for (int i = 0; i < 2; i++) {
        int x = s + k * di[i], y = t + dj[i] * k;
        if (valid(x, y) && !ok[k == -1][x][y]) {
            dfs(x, y, k);
        }
    }
}
void upd(int i, int j, int k) {
    bool tmp = false;
    for (int t = 0; t < 2; t++) {
        tmp |= valid(i - k * di[t], j - k * dj[t]) && ok[k == -1][i - k * di[t]][j - k * dj[t]];
    }
    if (tmp)
        return;
    if (ok[0][i][j] && ok[1][i][j])
        cnt[i + j]--;
    ok[k == -1][i][j] = false;
    for (int t = 0; t < 2; t++) {
        int x = i + di[t] * k, y = j + dj[t] * k;
        if (valid(x, y) && ok[k == -1][x][y])
            upd(x, y, k);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dfs(0, 0, 1);
    dfs(n - 1, m - 1, -1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cnt[i + j] += ok[0][i][j] && ok[1][i][j];
    int q; cin >> q;
    while (q--) {
        int i, j; cin >> i >> j;
        i--, j--;
        if (!ok[0][i][j] || !ok[1][i][j]) {
            cout << 1 << '\n';
            grid[i][j] = 1;
        }
        else if (cnt[i + j] > 1) {
            cout << 1 << '\n';
            grid[i][j] = 1;
            ok[0][i][j] = ok[1][i][j] = false;
            cnt[i + j]--;
            for (int t = 0; t < 2; t++) {
                int x = i + di[t], y = j + dj[t];
                int x2 = i - di[t], y2 = j - dj[t];
                if (valid(x, y) && ok[0][x][y])
                    upd(i + di[t], j + dj[t], 1);
                if (valid(x2, y2) && ok[1][x2][y2])
                    upd(i - di[t], j - dj[t], -1);
            }
        }
        else {
            cout << 0 << '\n';
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 9 ms 620 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 188 ms 4052 KB Output is correct
13 Correct 76 ms 3228 KB Output is correct
14 Correct 299 ms 4808 KB Output is correct
15 Correct 261 ms 4800 KB Output is correct
16 Correct 261 ms 5060 KB Output is correct
17 Correct 346 ms 5264 KB Output is correct
18 Correct 306 ms 5168 KB Output is correct
19 Correct 371 ms 5344 KB Output is correct
20 Correct 294 ms 5452 KB Output is correct
21 Correct 315 ms 5328 KB Output is correct