oj.uz

Submission #1019827

# Submission time Handle Problem Language Result Execution time Memory
1019827 2024-07-11T09:19:32 Z Andrey Furniture (JOI20_furniture) C++14
100 / 100
 1046 ms 74832 KB 
#include<bits/stdc++.h>
using namespace std;

int n,m;
int haha[1001][1001];
int bruh[1001][1001];
int wow[1001][1001];
int idk[1001][1001];

vector<int> sm(2000,INT_MAX);
vector<int> big(2000,-1);
vector<int> segs(5000);
vector<int> segb(5000);
set<int> no[1001];

void build(int l, int r, int x) {
    if(l == r) {
        segs[x] = sm[l];
        segb[x] = big[l];
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    segb[x] = max(segb[x*2],segb[x*2+1]);
    segs[x] = min(segs[x*2],segs[x*2+1]);
}

int calc(int l, int r, int ql, int qr, int x, bool yeah) {
    if(l == ql && r == qr) {
        if(yeah) {
            return segb[x];
        }
        else {
            return segs[x];
        }
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,x*2,yeah);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,x*2+1,yeah);
    }
    else {
        int a = calc(l,mid,ql,mid,x*2,yeah);
        int b = calc(mid+1,r,mid+1,qr,x*2+1,yeah);
        if(yeah) {
            return max(a,b);
        }
        else {
            return min(a,b);
        }
    }
}

void upd(int l, int r, int p, int x) {
    if(l == r) {
        segb[x] = big[p];
        segs[x] = sm[p];
        return;
    }
    int mid = (l+r)/2;
    if(p <= mid) {
        upd(l,mid,p,x*2);
    }
    else {
        upd(mid+1,r,p,x*2+1);
    }
    segb[x] = max(segb[x*2],segb[x*2+1]);
    segs[x] = min(segs[x*2],segs[x*2+1]);
}

void dfs1(int x, int y, bool yeah) {
    if(!yeah) {
        if(x < 0 || x >= n || y < 0 || y >= m) {
            return;
        }
        if(bruh[x][y] == 0) {
            return;
        }
        if(x > 0 && bruh[x-1][y]) {
            return;
        }
        if(y > 0 && bruh[x][y-1]) {
            return;
        }
    }
    bruh[x][y] = 0;
    idk[x][y] = 0;
    no[y].erase(x);
    sm[y] = *no[y].lower_bound(0);
    big[y] = *(--no[y].upper_bound(n-1));
    upd(0,m-1,y,1);
    dfs1(x+1,y,false);
    dfs1(x,y+1,false);
}

void dfs2(int x, int y, bool yeah) {
    if(!yeah) {
        if(x < 0 || x >= n || y < 0 || y >= m) {
            return;
        }
        if(wow[x][y] == 0) {
            return;
        }
        if(x < n-1 && wow[x+1][y]) {
            return;
        }
        if(y < m-1 && wow[x][y+1]) {
            return;
        }
    }
    wow[x][y] = 0;
    idk[x][y] = 0;
    no[y].erase(x);
    sm[y] = *no[y].lower_bound(0);
    big[y] = *(--no[y].upper_bound(n-1));
    upd(0,m-1,y,1);
    dfs2(x-1,y,false);
    dfs2(x,y-1,false);
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> haha[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            bruh[i][j] = 0;
            if(i > 0 && bruh[i-1][j]) {
                bruh[i][j] = 1;
            }
            if(j > 0 && bruh[i][j-1]) {
                bruh[i][j] = 1;
            }
            if(haha[i][j] == 1) {
                bruh[i][j] = 0;
            }
            if(i == 0 && j == 0) {
                bruh[i][j] = 1;
            }
        }
    }
    for(int i = n-1; i >= 0; i--) {
        for(int j = m-1; j >= 0; j--) {
            wow[i][j] = 0;
            if(i < n-1 && wow[i+1][j]) {
                wow[i][j] = 1;
            }
            if(j < m-1 && wow[i][j+1]) {
                wow[i][j] = 1;
            }
            if(haha[i][j] == 1) {
                wow[i][j] = 0;
            }
            if(i == n-1 && j == m-1) {
                wow[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < m; i++) {
        no[i].insert(-1);
        no[i].insert(n);
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            idk[i][j] = (bruh[i][j]&wow[i][j]);
            if(idk[i][j]) {
                sm[j] = min(sm[j],i);
                big[j] = max(big[j],i);
                no[j].insert(i);
            }
        }
    }
    build(0,m-1,1);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        if((y == 0 || calc(0,m-1,0,y-1,1,true) <= x) && (y == m-1 || calc(0,m-1,y+1,m-1,1,false) >= x)) {
            cout << 0 << "\n";
        }
        else {
            cout << 1 << "\n";
            dfs1(x,y,true);
            dfs2(x,y,true);
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 3 ms 2140 KB Output is correct
3 Correct 4 ms 2140 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 7 ms 2732 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 7 ms 2652 KB Output is correct
9 Correct 6 ms 2652 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 3 ms 2140 KB Output is correct
3 Correct 4 ms 2140 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 7 ms 2732 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 7 ms 2652 KB Output is correct
9 Correct 6 ms 2652 KB Output is correct
10 Correct 17 ms 1896 KB Output is correct
11 Correct 6 ms 1552 KB Output is correct
12 Correct 832 ms 56716 KB Output is correct
13 Correct 254 ms 42584 KB Output is correct
14 Correct 1038 ms 59656 KB Output is correct
15 Correct 931 ms 64952 KB Output is correct
16 Correct 806 ms 69200 KB Output is correct
17 Correct 854 ms 73120 KB Output is correct
18 Correct 1046 ms 70864 KB Output is correct
19 Correct 877 ms 74832 KB Output is correct
20 Correct 828 ms 74756 KB Output is correct
21 Correct 661 ms 74720 KB Output is correct