Submission #1145758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145758		fatman87878	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	1604 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=1e3+5;

int n,m,q,cnt[maxN+maxN],c[maxN][maxN],deg[maxN][maxN],ged[maxN][maxN];

queue<pair<int,int>> qup,qdwn;

inline bool chk(int x,int y){
    if(x>n||x<1||y>m||y<1||c[x][y])return 0;
    return 1;
}

inline void push_up(){
    for(int x,y;!qup.empty();){
        tie(x,y) = qup.front(),qup.pop();
        cnt[x+y]--;
        c[x][y] = 1;
        if(chk(x-1,y)&&!(--ged[x-1][y]))qup.emplace(x-1,y);
        if(chk(x,y-1)&&!(--ged[x][y-1]))qup.emplace(x,y-1);
    }
}

inline void push_down(){
    for(int x,y;!qdwn.empty();){
        tie(x,y) = qdwn.front(),qdwn.pop();
        cnt[x+y]--;
        c[x][y] = 1;
        if(chk(x+1,y)&&!(--deg[x+1][y]))qdwn.emplace(x+1,y);
        if(chk(x,y+1)&&!(--deg[x][y+1]))qdwn.emplace(x,y+1);
    }
}

int main(){
    IOS
    cin>>n>>m;
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++){
        cin>>c[i][j],cnt[i+j]++;
        if(c[i][j])qup.emplace(i,j),qdwn.emplace(i,j);
    }
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(!c[i][j])ged[i][j] = (i!=n)+(j!=m);
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(!c[i][j])deg[i][j] = (i!=1)+(j!=1);
    push_up();
    push_down();
    cin>>q;
    for(int x,y;q--;){
        cin>>x>>y;
        if(c[x][y]||cnt[x+y]>1){
            if(!c[x][y]){
                qup.emplace(x,y);
                qdwn.emplace(x,y);
                deg[x][y] = 0;
                ged[x][y] = 0;
                push_up();
                push_down();
            }
            cout<<"1\n";
        }
        else cout<<"0\n";
    }
}

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