제출 #784563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784563		hanifchdn	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	1108 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

const int dx[] = {0, 1};
const int dy[] = {1, 0};

int n, m;
bool a[1005][1005], check[1005][1005], vis[1005][1005];
set<int> s1[1005], s2[1005];

void dfs(int x, int y) {
    vis[x][y] = 1;
    if (a[x][y]) return;
    for (int i = 0; i < 2; i++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx > n or ty > m) continue;
        if (!vis[tx][ty]) dfs(tx, ty);
        check[x][y] |= check[tx][ty];
    }
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vis[n][m] = 1, check[n][m] = 1;
    dfs(1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] and check[i][j - 1]) s1[j].insert(i);
            if (check[i][j] and check[i - 1][j]) s2[i].insert(j);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (!check[x][y]) cout << 1 << "\n";
        else {
            auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y);
            if (it1 == s1[y].end() and it2 == s2[x].end()) {
                cout << 0 << "\n";
                continue;
            }
            cout << 1 << "\n";
            check[x][y] = 0, s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y);
            for (int i = x + 1; i <= n; i++) {
                if (!check[i][y] or check[i][y - 1]) break;
                check[i][y] = 0;
                s2[i + 1].erase(y), s1[y].erase(i + 1);
            }
            for (int j = y + 1; j <= m; j++) {
                if (!check[x][j] or check[x - 1][j]) break;
                check[x][j] = 0;
                s1[j + 1].erase(x), s2[x].erase(j + 1);
            }
            for (int i = x - 1; i >= 1; i--) {
                if (!check[i][y] or check[i][y + 1]) break;
                check[i][y] = 0;
                s2[i].erase(y), s1[y].erase(i);
            }
            for (int j = y - 1; j >= 1; j--) {
                if (!check[x][j] or check[x + 1][j]) break;
                check[x][j] = 0;
                s1[j].erase(x), s2[x].erase(j);
            }
        }
    }
}  

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