Submission #772586

#	Time	Username	Problem	Language	Result	Execution time	Memory
772586		gagik_2007	Furniture (JOI20_furniture)	C++17	0 / 100	251 ms	524288 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
const ll LG=25;
ll n,m,k;
bool a[N][N];
bool bl[N][N];
bool ur[N][N];
bool used[N][N];
set<int>dt[N];
set<int>dc[N];
int urc[N], urt[N];
int blc[N], blt[N];

void kpcruBL(int i, int j){
    for(int jj=blt[i]+1;jj<=j;jj++){
        a[i][jj]=true;
        bl[i][jj]=true;
    }
    for(int ii=i;ii<blc[j];ii++){
        a[ii][j]=true;
        bl[ii][j]=true;
    }
}

void kpcruUR(int i, int j){
    for(int jj=j;jj<blt[i];jj++){
        a[i][jj]=true;
        ur[i][jj]=true;
    }
    for(int ii=blc[j]+1;ii<=i;ii++){
        a[ii][j]=true;
        ur[ii][j]=true;
    }
}

void gnaUR(int i, int j){
    kpcruUR(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
                gnaUR(ii,jj);
            }
        }
    }
}

void gnaBL(int i, int j){
    kpcruBL(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
                gnaBL(ii,jj);
            }
        }
    }
}

int query(int i, int j){
    bool urka=false;
    bool blka=false;
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)){
                if(ur[ii][jj])urka=true;
                if(bl[ii][jj])blka=true;
            }
        }
    }
    if(urka&&blka)return 0;
    if(urka){
        gnaUR(i,j);
    }
    if(blka){
        gnaBL(i,j);
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(i==0||i==n+1||j==0||j==m+1){
                a[i][j]=true;
                if(i==0||j==m+1)ur[i][j]=true;
                else bl[i][j]=true;
                continue;
            }
            cin>>a[i][j];
            if(a[i][j]){
                dt[i].insert(j);
                dc[j].insert(i);
            }
        }
    }
    urt[0]=0;
    urc[m+1]=n;
    for(int i=1;i<=n;i++){
        auto it=dt[i].lower_bound(urt[i-1]-1);
        urt[i]=m+10;
        if(it!=dt[i].end())urt[i]=*it;
        for(int j=m;j>=1;j--){
            auto itt=dc[j].upper_bound(urc[j+1]+1);
            urc[j]=-10;
            if(itt!=dc[j].begin())urc[j]=*(--itt);
            if(urt[i]<=j||urc[j]>=i){
                a[i][j]=true;
                ur[i][j]=true;
                dt[i].insert(j);
                dc[j].insert(i);
            }
        }
    }
    blt[n+1]=m;
    blc[0]=0;
    for(int i=n;i>=1;i--){
        auto it=dt[i].upper_bound(blt[i+1]+1);
        blt[i]=-10;
        if(it!=dt[i].begin())blt[i]=*(--it);
        // cout<<"i - "<<i<<": "<<blt[i]<<endl;
        for(int j=1;j<=m;j++){
            // cout<<"dc: ";
            // for(int x:dc[j]){
            //     cout<<x<<" ";
            // }
            // cout<<endl;
            auto itt=dc[j].lower_bound(blc[j-1]-1);
            blc[j]=n+10;
            if(itt!=dc[j].end())blc[j]=*itt;
            // cout<<"j - "<<j<<": "<<blc[j]<<endl;
            if(blt[i]>=j||blc[j]<=i){
                a[i][j]=true;
                // cout<<i<<", "<<j<<": "<<blt[i]<<" "<<blc[j]<<endl;
                bl[i][j]=true;
                dt[i].insert(j);
                dc[j].insert(i);
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<a[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<bl[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<ur[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    cin>>k;
    for(int c=0;c<k;c++){
        int i,j;
        cin>>i>>j;
        cout<<query(i,j)<<endl;
    // assert(false);
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95