oj.uz

Submission #929221

# Submission time Handle Problem Language Result Execution time Memory
929221 2024-02-18T01:36:12 Z 1075508020060209tc Furniture (JOI20_furniture) C++14
100 / 100
 1695 ms 35956 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>>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 4952 KB Output is correct
2 Correct 6 ms 7316 KB Output is correct
3 Correct 8 ms 7260 KB Output is correct
4 Correct 13 ms 7260 KB Output is correct
5 Correct 14 ms 7436 KB Output is correct
6 Correct 17 ms 7256 KB Output is correct
7 Correct 17 ms 7256 KB Output is correct
8 Correct 17 ms 7260 KB Output is correct
9 Correct 16 ms 7440 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 6 ms 7316 KB Output is correct
3 Correct 8 ms 7260 KB Output is correct
4 Correct 13 ms 7260 KB Output is correct
5 Correct 14 ms 7436 KB Output is correct
6 Correct 17 ms 7256 KB Output is correct
7 Correct 17 ms 7256 KB Output is correct
8 Correct 17 ms 7260 KB Output is correct
9 Correct 16 ms 7440 KB Output is correct
10 Correct 42 ms 5456 KB Output is correct
11 Correct 11 ms 4696 KB Output is correct
12 Correct 612 ms 28712 KB Output is correct
13 Correct 142 ms 25792 KB Output is correct
14 Correct 1385 ms 33464 KB Output is correct
15 Correct 1421 ms 33332 KB Output is correct
16 Correct 1530 ms 34472 KB Output is correct
17 Correct 1632 ms 35484 KB Output is correct
18 Correct 1501 ms 34784 KB Output is correct
19 Correct 1619 ms 35868 KB Output is correct
20 Correct 1593 ms 35956 KB Output is correct
21 Correct 1695 ms 35868 KB Output is correct