Submission #1143418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143418		browntoad	Furniture (JOI20_furniture)	C++20	100 / 100	385 ms	18272 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 1005;
const ll mod = 998244353;
const ll inf = (1ll<<60);

ll pw(ll x, ll p, ll m){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= x;
            ret %= m;
        }
        x *= x;
        x %= m;
        p >>= 1;
    }
    return ret;
}
ll inv(ll x, ll m){
    return pw(x, m-2, m);
}

int rchst[maxn][maxn], rchen[maxn][maxn], rch[maxn][maxn];
int num[2*maxn];
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

int n, m;
int arr[maxn][maxn];

bool ok(pii c){
    int a = c.f, b = c.s;
    if (arr[a][b]) return 0;
    return (a <= n && a >= 1 && b <= m && b >= 1);
}
void init(){
    queue<pii> iq; iq.push({1, 1});
    while(SZ(iq)){
        pii cur = iq.front(); iq.pop();
        if (rchst[cur.f][cur.s]) continue;
        rchst[cur.f][cur.s] = 1;
        REP(i, 2){
            pii ncur = {cur.f + dx[i], cur.s + dy[i]};
            if (ok(ncur) && !rchst[ncur.f][ncur.s]){
                iq.push(ncur);
            }
        }
    }

    iq.push({n, m});
    while(SZ(iq)){
        pii cur = iq.front(); iq.pop();
        if (rchen[cur.f][cur.s]) continue;
        rchen[cur.f][cur.s] = 1;
        REP(i, 2){
            pii ncur = {cur.f + dx[3-i], cur.s + dy[3-i]};
            if (ok(ncur) && !rchen[ncur.f][ncur.s]){
                iq.push(ncur);
            }
        }
    }

    REP1(i, n){
        REP1(j, m){
            if (!rchst[i][j] || !rchen[i][j]){
                rch[i][j] = 0;
                num[i+j]--;
            }
            else rch[i][j] = 1;
        }
    }
}

void upd(pii a){
    if (rch[a.f][a.s]){
        if (!rchen[a.f][a.s] || !rchst[a.f][a.s]){
            rch[a.f][a.s] = 0;
            num[a.f+a.s]--;
        }
    }
}
void updNW(pii cur){
    if (!rchen[cur.f][cur.s]) return;
    rchen[cur.f][cur.s] = 0;
    upd(cur);
    REP(i, 2){
        pii ncur = {cur.f + dx[3-i], cur.s + dy[3-i]};
        if (ok(ncur) && rchen[ncur.f][ncur.s] && !rchen[ncur.f+1][ncur.s] && !rchen[ncur.f][ncur.s+1]){
            updNW(ncur);
        }
    }
}
void updSE(pii cur){
    if (!rchst[cur.f][cur.s]) return;
    rchst[cur.f][cur.s] = 0;
    upd(cur);
    REP(i, 2){
        pii ncur = {cur.f + dx[i], cur.s + dy[i]};
        if (ok(ncur) && rchst[ncur.f][ncur.s] && !rchst[ncur.f-1][ncur.s] && !rchst[ncur.f][ncur.s-1]){
            updSE(ncur);
        }
    }
}
signed main(){
    IOS();
    cin>>n>>m;
    REP1(i, n) REP1(j, m) {
        cin>>arr[i][j];
        num[i+j]++;
    }
    init();

    int q; cin>>q;
    while(q--){
        pii in; cin>>in.f>>in.s;
        if (num[in.f+in.s] == 1 && rch[in.f][in.s]){ // only one remaining in diagonal
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;

        updNW(in);
        updSE(in);
    }


}

/*
3 3
0 0 0
0 0 0
0 0 0
3
1 2
2 2
3 2
*/

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