Submission #1039281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039281		a_l_i_r_e_z_a	Furniture (JOI20_furniture)	C++17	100 / 100	712 ms	117844 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long long ll;
typedef long double ld;

#define mp make_pair
// #define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define F first
#define S second

const int maxn = 1e3 + 5; 
const int inf = 1e9 + 7;
int n, m, dp[maxn][maxn][2], a[maxn][maxn];
set<int> stc[maxn], str[maxn];

void dfs0(int i, int j){
    dp[i][j][0] = 1;
    if(dp[i][j][1] == 0){
        stc[j].erase(i);
        str[i].erase(j);
    }
    if(j < m - 1){
        if(dp[i][j + 1][0] == 0 && (i == 0 || dp[i - 1][j + 1][0] == 1)){
            dfs0(i, j + 1);
        }
    }
    if(i < n - 1){
        if(dp[i + 1][j][0] == 0 && (j == 0 || dp[i + 1][j - 1][0] == 1)){
            dfs0(i + 1, j);
        }
    }
}

void dfs1(int i, int j){
    dp[i][j][1] = 1;
    if(dp[i][j][0] == 0){
        stc[j].erase(i);
        str[i].erase(j);
    }
    if(j > 0){
        if(dp[i][j - 1][1] == 0 && (i == n - 1 || dp[i + 1][j - 1][1] == 1)){
            dfs1(i, j - 1);
        }
    }
    if(i > 0){
        if(dp[i - 1][j][1] == 0 && (j == m - 1 || dp[i - 1][j + 1][1] == 1)){
            dfs1(i - 1, j);
        }
    }
}

bool roshan(int x, int y){
    bool ans = 0;
    if(y < m - 1){
        if(stc[y + 1].size() && (*stc[y + 1].begin()) < x){
            ans = 1;
        }
    }
    if(x < n - 1){
        if(str[x + 1].size() && (*str[x + 1].begin()) < y){
            ans = 1;
        }
    }
    if(ans == 0) return 0;
    dfs0(x, y);
    dfs1(x, y);
    return 1;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            str[i].insert(j);
            stc[j].insert(i);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) if(a[i][j] == 1) roshan(i, j);
    }
    int q; cin >> q;
    while(q--){
        int i, j; cin >> i >> j;
        i--, j--;
        cout << roshan(i, j) << '\n';
    }

    return 0;
}

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