oj.uz

Submission #331863

# Submission time Handle Problem Language Result Execution time Memory
331863 2020-11-30T14:32:36 Z phathnv Furniture (JOI20_furniture) C++11
100 / 100
 373 ms 21136 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

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

const int N = 1002;
const int dx[8] = {-1, 0, 0, 1};
const int dy[8] = {0, -1, 1, 0};

int m, n, q, a[N][N], imp[N][N], cnt[2 * N];
bool d[N][N];

void readInput(){
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
}

void update(int x, int y){
    if (!imp[x][y])
        return;
    imp[x][y] = 0;
    cnt[x + y]--;
    if (!imp[x - 1][y + 1]){
        update(x - 1, y);
        update(x, y + 1);
    }
    if (!imp[x + 1][y - 1]){
        update(x, y - 1);
        update(x + 1, y);
    }
}

void solve(){
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            imp[i][j] = 1;

    memset(d, 0, sizeof(d));
    d[1][1] = 1;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++){
            d[i][j] |= d[i - 1][j];
            d[i][j] |= d[i][j - 1];
            if (a[i][j])
                d[i][j] = 0;
            imp[i][j] &= d[i][j];
        }

    memset(d, 0, sizeof(d));
    d[m][n] = 1;
    for(int i = m; i >= 1; i--)
        for(int j = n; j >= 1; j--){
            d[i][j] |= d[i + 1][j];
            d[i][j] |= d[i][j + 1];
            if (a[i][j])
                d[i][j] = 0;
            imp[i][j] &= d[i][j];
        }

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if (imp[i][j])
                cnt[i + j]++;

    cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        if (!imp[x][y]){
            cout << "1\n";
            continue;
        }
        if (cnt[x + y] == 1){
            cout << "0\n";
            continue;
        }
        update(x, y);
        cout << "1\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1900 KB Output is correct
2 Correct 2 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 4 ms 2304 KB Output is correct
6 Correct 4 ms 2284 KB Output is correct
7 Correct 4 ms 2284 KB Output is correct
8 Correct 5 ms 2284 KB Output is correct
9 Correct 4 ms 2284 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1900 KB Output is correct
2 Correct 2 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 4 ms 2304 KB Output is correct
6 Correct 4 ms 2284 KB Output is correct
7 Correct 4 ms 2284 KB Output is correct
8 Correct 5 ms 2284 KB Output is correct
9 Correct 4 ms 2284 KB Output is correct
10 Correct 10 ms 2156 KB Output is correct
11 Correct 3 ms 1772 KB Output is correct
12 Correct 162 ms 13740 KB Output is correct
13 Correct 72 ms 10732 KB Output is correct
14 Correct 349 ms 18388 KB Output is correct
15 Correct 287 ms 18540 KB Output is correct
16 Correct 324 ms 19820 KB Output is correct
17 Correct 330 ms 20460 KB Output is correct
18 Correct 304 ms 19960 KB Output is correct
19 Correct 360 ms 20844 KB Output is correct
20 Correct 282 ms 21136 KB Output is correct
21 Correct 373 ms 20972 KB Output is correct