oj.uz

Submission #402531

# Submission time Handle Problem Language Result Execution time Memory
402531 2021-05-11T22:45:46 Z rqi Furniture (JOI20_furniture) C++14
100 / 100
 2401 ms 21812 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()

const int mx = 1005;
int N, M;
bool C[mx][mx];
bool disap[mx][mx];
pi deg[mx][mx];//leftup, rightdown degree
queue<pi> to_remove;
int maxrow[mx];
int maxcol[mx];

void subDeg(int X, int Y, bool typ){
    if(C[X][Y] || disap[X][Y]) return;
    if(mp(X, Y) == mp(1, 1) || mp(X, Y) == mp(N, M)) return;
    if(typ == 0){
        deg[X][Y].f--;
    }
    else{
        deg[X][Y].s--;
    }
    if(deg[X][Y].f == 0 || deg[X][Y].s == 0){
        to_remove.push(mp(X, Y));
        disap[X][Y] = 1;
    }
}

void removeToRemoves(){
    while(sz(to_remove)){
        pi coor = to_remove.front();
        to_remove.pop();
        disap[coor.f][coor.s] = 0;
        C[coor.f][coor.s] = 1;
        subDeg(coor.f-1, coor.s, 1);
        subDeg(coor.f, coor.s-1, 1);
        subDeg(coor.f+1, coor.s, 0);
        subDeg(coor.f, coor.s+1, 0);
    }
}

void updateMaxes(int X, int Y){
    while(maxrow[X]+1 <= M){
        if(C[X][maxrow[X]+1]){
            maxrow[X]++;
            continue;
        }
        else{
            break;
        }
    }
    while(maxcol[Y]+1 <= N){
        if(C[maxcol[Y]+1][Y]){
            maxcol[Y]++;
            continue;
        }
        else{
            break;
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> C[i][j];
        }
    }
    for(int i = 0; i <= N+1; i++){
        C[i][0] = C[i][M+1] = 1;
    }
    for(int i = 0; i <= M+1; i++){
        C[0][i] = C[N+1][i] = 1;
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(mp(i, j) == mp(1, 1) || mp(i, j) == mp(N, M)) continue;
            if(C[i][j]) continue;
            deg[i][j].f+=(int)(!C[i-1][j])+(int)(!C[i][j-1]);
            deg[i][j].s+=(int)(!C[i+1][j])+(int)(!C[i][j+1]);
            if(deg[i][j].f == 0 || deg[i][j].s == 0){
                to_remove.push(mp(i, j));
                disap[i][j] = 1;
            }
        }
    }

    int Q;
    cin >> Q;
    for(int i = 1; i <= Q; i++){
        //cout << "QUERY: " << i << "\n";
        int X, Y;
        cin >> X >> Y;
        removeToRemoves();
        updateMaxes(X+1, Y+1);
        // for(int i = 1; i <= N; i++){
        //     for(int j = 1; j <= M; j++){
        //         cout << C[i][j] << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        // for(int i = 1; i <= N; i++){
        //     for(int j = 1; j <= M; j++){
        //         cout << deg[i][j].f << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        // for(int i = 1; i <= N; i++){
        //     for(int j = 1; j <= M; j++){
        //         cout << deg[i][j].s << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        if(C[X][Y] == 0 && maxrow[X+1] >= Y-1 && maxcol[Y+1] >= X-1){
            cout << 0 << "\n";
        }
        else{
            cout << 1 << "\n";
            if(C[X][Y] == 0){
                to_remove.push(mp(X, Y));
                disap[X][Y] = 1;
            }
            
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 10 ms 844 KB Output is correct
3 Correct 11 ms 956 KB Output is correct
4 Correct 19 ms 1040 KB Output is correct
5 Correct 21 ms 1076 KB Output is correct
6 Correct 28 ms 1100 KB Output is correct
7 Correct 26 ms 1088 KB Output is correct
8 Correct 25 ms 972 KB Output is correct
9 Correct 24 ms 1092 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 10 ms 844 KB Output is correct
3 Correct 11 ms 956 KB Output is correct
4 Correct 19 ms 1040 KB Output is correct
5 Correct 21 ms 1076 KB Output is correct
6 Correct 28 ms 1100 KB Output is correct
7 Correct 26 ms 1088 KB Output is correct
8 Correct 25 ms 972 KB Output is correct
9 Correct 24 ms 1092 KB Output is correct
10 Correct 64 ms 1228 KB Output is correct
11 Correct 16 ms 768 KB Output is correct
12 Correct 899 ms 14704 KB Output is correct
13 Correct 236 ms 11776 KB Output is correct
14 Correct 2000 ms 19120 KB Output is correct
15 Correct 2044 ms 19464 KB Output is correct
16 Correct 2212 ms 20252 KB Output is correct
17 Correct 2341 ms 21236 KB Output is correct
18 Correct 2300 ms 21012 KB Output is correct
19 Correct 2401 ms 21668 KB Output is correct
20 Correct 2382 ms 21764 KB Output is correct
21 Correct 2398 ms 21812 KB Output is correct