Submission #929219

#	Time	Username	Problem	Language	Result	Execution time	Memory
929219		1075508020060209tc	Furniture (JOI20_furniture)	C++14	0 / 100	19 ms	20572 KiB

furniture

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n;int m;int Q;
int gr[1010][1010];
int rch[1010][1010];
int rrch[1010][1010];
int okcnt[3010];

void precalc(){
queue<pair<int,int>>q;
q.push({1,1});
rch[1][1]=1;
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    int x=nwx;int y=nwy;
    x++;
    if(gr[x][y]==0&&rch[x][y]==0){
        rch[x][y]=1;
        q.push({x,y});
    }
    x--;y++;
    if(gr[x][y]==0&&rch[x][y]==0){
        rch[x][y]=1;
        q.push({x,y});
    }
}


q.push({n,m});
rch[n][m]=1;
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    int x=nwx;int y=nwy;
    x--;
    if(gr[x][y]==0&&rrch[x][y]==0){
        rrch[x][y]=1;
        q.push({x,y});
    }
    x++;y--;
    if(gr[x][y]==0&&rrch[x][y]==0){
        rrch[x][y]=1;
        q.push({x,y});
    }
}
}

void bkupd(int stx,int sty){
queue<pair<int,int>>q;
q.push({stx,sty});
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    int x=nwx-1;int y=nwy;
    if(rrch[x][y]==1&&rrch[x][y+1]==0){
        rrch[x][y]=0;
        if(rch[x][y]==1){
            okcnt[x+y]--;
        }
        q.push({x,y});
    }
    x=nwx;y=nwy-1;
    if(rrch[x][y]==1&&rrch[x+1][y]==0){
        rrch[x][y]=0;
        if(rch[x][y]==1){
            okcnt[x+y]--;
        }
        q.push({x,y});
    }
}


}

void frupd(int stx,int sty){
queue<pair<int,int>>q;
q.push({stx,sty});
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    int x=nwx+1;int y=nwy;
    if(rch[x][y]==1&&rch[x][y-1]==0){
        rch[x][y]=0;
        if(rrch[x][y]==1){
            okcnt[x+y]--;
        }
        q.push({x,y});
    }
    x=nwx;y=nwy+1;
    if(rch[x][y]==1&&rch[x-1][y]==0){
        rch[x][y]=0;
        if(rrch[x][y]==1){
            okcnt[x+y]--;
        }
        q.push({x,y});
    }
}
}


signed main(){

cin>>n>>m;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>gr[i][j];
    }
}
precalc();
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(rch[i][j]&&rrch[i][j]){
            okcnt[i+j]++;
        }
    }
}
cin>>Q;
while(Q--){
    int x;int y;
    cin>>x>>y;
    if(rch[x][y]&&rrch[x][y]){
        if(okcnt[x+y]==1){
            cout<<0<<"\n";
            continue;
        }
    }
    if(rch[x][y]){
        frupd(x,y);
    }
    if(rrch[x][y]){
        bkupd(x,y);
    }


    if(rch[x][y]&&rrch[x][y]){okcnt[x+y]--;}
    rch[x][y]=0;rrch[x][y]=0;
    cout<<"1\n";
}



}

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