Submission #362156

#	Time	Username	Problem	Language	Result	Execution time	Memory
362156		doowey	Furniture (JOI20_furniture)	C++14	100 / 100	419 ms	8684 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1010;
int C[N][N];
bool is_up[N][N];
bool is_down[N][N];
int low_y[N];
int low_x[N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> C[i][j];
        }
    }
    for(int i = 1; i <= n; i ++ ){
        low_x[i] = 1;
    }
    for(int i = 1; i <= m; i ++ ){
        low_y[i] = 1;
    }
    is_up[1][1]=true;
    is_down[n][m]=true;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            if(i == 1 && j == 1) continue;
            if(C[i][j]==1) continue;
            is_up[i][j] = (is_up[i][j-1]|is_up[i-1][j]);
        }
    }
    for(int i = n; i >= 1; i -- ){
        for(int j = m ; j >= 1; j -- ){
            if(i==n && j == m) continue;
            if(C[i][j]==1) continue;
            is_down[i][j] = (is_down[i+1][j]|is_down[i][j+1]);
        }
    }
    int q;
    cin >> q;
    int xi, yi;
    bool keep;
    int ci, cj;
    for(int qr = 1; qr <= q; qr ++ ){
        cin >> xi >> yi;
        if(!is_up[xi][yi] || !is_down[xi][yi]){
            C[xi][yi]=1;
            cout << 1 << "\n";
        }
        else{
            while(low_y[yi] < xi){
                if(!is_up[low_y[yi]][yi] || !is_down[low_y[yi]][yi+1]) low_y[yi] ++ ;
                else break;
            }
            while(low_x[xi] < yi){
                if(!is_up[xi][low_x[xi]] || !is_down[xi+1][low_x[xi]]) low_x[xi] ++ ;
                else break;
            }
            if(low_y[yi] < xi || low_x[xi] < yi) keep = true;
            else keep = false;
            if(keep == true){
                C[xi][yi]=0;
                is_up[xi][yi]=false;
                is_down[xi][yi]=false;
                queue<pii> qq;
                qq.push(mp(xi,yi));
                while(!qq.empty()){
                    ci = qq.front().fi;
                    cj = qq.front().se;
                    qq.pop();
                    if(is_up[ci+1][cj] && !is_up[ci+1][cj-1]){
                        is_up[ci+1][cj]=false;
                        qq.push(mp(ci+1,cj));
                    }
                    if(is_up[ci][cj+1] && !is_up[ci-1][cj+1]){
                        is_up[ci][cj+1]=false;
                        qq.push(mp(ci,cj+1));
                    }
                }
                qq.push(mp(xi,yi));
                while(!qq.empty()){
                    ci = qq.front().fi;
                    cj = qq.front().se;
                    qq.pop();
                    if(is_down[ci-1][cj] && !is_down[ci-1][cj+1]){
                        is_down[ci-1][cj]=false;
                        qq.push(mp(ci-1,cj));
                    }
                    if(is_down[ci][cj-1] && !is_down[ci+1][cj-1]){
                        is_down[ci][cj-1]=false;
                        qq.push(mp(ci,cj-1));
                    }
                }
                cout << "1\n";
            }
            else{
                cout << "0\n";
            }
        }
    }
    return 0;
}

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