Submission #1264154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264154		domi	Furniture (JOI20_furniture)	C++20	100 / 100	187 ms	26108 KiB

furniture

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e3;
const int dlin[] = {1, 0};
const int dcol[] = {0, 1};

using namespace std;

int mat[NMAX + 5][NMAX + 5], reachable_sus[NMAX + 5][NMAX + 5], reachable_jos[NMAX + 5][NMAX + 5], diag[2 * NMAX + 5], n, m, q;

bool inbound(int r, int c) {
    return (r >= 1 && r <= n && c >= 1 && c <= m);
}

void update_sus(int r, int c) {
    diag[r + c] -= reachable_sus[r][c] * reachable_jos[r][c];
    reachable_sus[r][c] = false;

    for (int dir = 0; dir < 2; ++dir) {
        int x = r + dlin[dir];
        int y = c + dcol[dir];

        if (inbound(x, y) && reachable_sus[x][y] && !reachable_sus[x - 1][y] && !reachable_sus[x][y - 1])
            update_sus(x, y);
    }
}

void update_jos(int r, int c) {
    diag[r + c] -= reachable_sus[r][c] * reachable_jos[r][c];
    reachable_jos[r][c] = false;

    for (int dir = 0; dir < 2; ++dir) {
        int x = r - dlin[dir];
        int y = c - dcol[dir];

        if (inbound(x, y) && reachable_jos[x][y] && !reachable_jos[x + 1][y] && !reachable_jos[x][y + 1])
            update_jos(x, y);
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

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

    reachable_sus[1][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mat[i][j] == 1)
                reachable_sus[i][j] = 0;

            for (int dir = 0; dir < 2; ++dir) {
                int x = i + dlin[dir];
                int y = j + dcol[dir];
                if (inbound(x, y))
                    reachable_sus[x][y] |= reachable_sus[i][j];
            }
        }
    }

    reachable_jos[n][m] = 1;
    for (int i = n; i >= 1; --i) {
        for (int j = m; j >= 1; --j) {
            if (mat[i][j] == 1)
                reachable_jos[i][j] = 0;

            for (int dir = 0; dir < 2; ++dir) {
                int x = i - dlin[dir];
                int y = j - dcol[dir];
                if (inbound(x, y))
                    reachable_jos[x][y] |= reachable_jos[i][j];
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            diag[i + j] += reachable_sus[i][j] * reachable_jos[i][j];

    cin >> q;
    for (int i = 0, x, y; i < q; ++i) {
        cin >> x >> y;
        if (reachable_sus[x][y] && reachable_jos[x][y] && diag[x + y] == 1){
            cout << "0\n";
            continue;
        }

        if (reachable_sus[x][y])
            update_sus(x, y);

        if (reachable_jos[x][y])
            update_jos(x, y);

        cout << "1\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95