oj.uz

Submission #929222

# Submission time Handle Problem Language Result Execution time Memory
929222 2024-02-18T01:37:46 Z 1075508020060209tc Furniture (JOI20_furniture) C++14
100 / 100
 249 ms 14416 KB 
//#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];
int ok(int x,int y){
if(x>=1&&y>=1&&x<=n&&y<=m){return 1;}
return 0;
}
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&&ok(x,y)){
        rch[x][y]=1;
        q.push({x,y});
    }
    x--;y++;
    if(gr[x][y]==0&&rch[x][y]==0&&ok(x,y)){
        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&&ok(x,y)){
        rrch[x][y]=1;
        q.push({x,y});
    }
    x++;y--;
    if(gr[x][y]==0&&rrch[x][y]==0&&ok(x,y)){
        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.tie(0);
ios_base::sync_with_stdio(0);
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 7152 KB Output is correct
6 Correct 4 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 3 ms 7004 KB Output is correct
9 Correct 3 ms 7156 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 7152 KB Output is correct
6 Correct 4 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 3 ms 7004 KB Output is correct
9 Correct 3 ms 7156 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 135 ms 12712 KB Output is correct
13 Correct 57 ms 12240 KB Output is correct
14 Correct 214 ms 13524 KB Output is correct
15 Correct 222 ms 13660 KB Output is correct
16 Correct 249 ms 13904 KB Output is correct
17 Correct 226 ms 14260 KB Output is correct
18 Correct 224 ms 13908 KB Output is correct
19 Correct 202 ms 14416 KB Output is correct
20 Correct 235 ms 14180 KB Output is correct
21 Correct 236 ms 14416 KB Output is correct