Submission #1019827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019827		Andrey	Furniture (JOI20_furniture)	C++14	100 / 100	1046 ms	74832 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95