Submission #715650

#	Time	Username	Problem	Language	Result	Execution time	Memory
715650		Makarooni	Furniture (JOI20_furniture)	C++17	100 / 100	534 ms	61156 KiB

furniture

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

#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define endl '\n'
#define sz(x) (int)x.size()
#define mr(x, y) make_pair(x, y)
#define F first
#define S second

const int N = 2e3 + 10;
const int MOD = 1e9 + 7;

int c[N][N], x[N][N], y[N][N], n, m, cnt[N * 2];
priority_queue<pair<int, int>> st, st2;
bool bl[N][N];

int f(int i, int j){
    return (i - 1) * m + j;
}

void upd(int i, int j){
    if(bl[i][j])
        return;
    bl[i][j] = 1;
    cnt[i + j]--;
    if(i - 1 > 0 && !bl[i - 1][j]){
        x[i - 1][j]--;
        st.push(mr(-x[i - 1][j], f(i - 1, j)));
    }
    if(j - 1 > 0 && !bl[i][j - 1]){
        x[i][j - 1]--;
        st.push(mr(-x[i][j - 1], f(i, j - 1)));
    }
    if(i + 1 <= n && !bl[i + 1][j]){
        y[i + 1][j]--;
        st2.push(mr(-y[i + 1][j], f(i + 1, j)));
    }
    if(j + 1 <= m && !bl[i][j + 1]){
        y[i][j + 1]--;
        st2.push(mr(-y[i][j + 1], f(i, j + 1)));
    }
}

int main(){
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    bl[1][1] = 1;
    bl[n][m] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == j && i == 1)
                continue;
            if(i == n && j == m)
                continue;
            y[i][j] = (i - 1 > 0) + (j - 1 > 0);
            x[i][j] = (i + 1 <= n) + (j + 1 <= m);
            cnt[i + j]++;
            st.push(mr(-x[i][j], f(i, j)));
            st2.push(mr(-y[i][j], f(i, j)));
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c[i][j];
            if(!c[i][j])
                continue;
            upd(i, j);
        }
    }
    while(min(-st.top().F, -st2.top().F) == 0){
        if(st.top().F == 0){
            int r = st.top().S, t;
            t = r % m;
            if(t == 0)
                t = m;
            st.pop();
            upd(r / m + (t != m), t);
        }
        else{
            int r = st2.top().S, t;
            t = r % m;
            if(t == 0)
                t = m;
            st2.pop();
            upd(r / m + (t != m), t);
        }
    }
    int p, q, Q;
    cin >> Q;
    while(Q--){
        cin >> p >> q;
        if(bl[p][q])
            cout << 1 << endl;
        else if(cnt[p + q] == 1)
            cout << 0 << endl;
        else{
            cout << 1 << endl;
            upd(p, q);
            while(min(-st.top().F, -st2.top().F) == 0){
                if(st.top().F == 0){
                    int r = st.top().S, t;
                    t = r % m;
                    if(t == 0)
                        t = m;
                    st.pop();
                    upd(r / m + (t != m), t);
                }
                else{
                    int r = st2.top().S, t;
                    t = r % m;
                    if(t == 0)
                        t = m;
                    st2.pop();
                    upd(r / m + (t != m), t);
                }
            }
        }
    }
}

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