Submission #1088824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088824		Wansur	Furniture (JOI20_furniture)	C++14	100 / 100	2619 ms	52308 KiB

furniture

#include <bits/stdc++.h>
#define ent '\n'
#define int long long

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 12;

int dp[1050][1050];
int a[1050][1050];
int t[1050][1050];
int ans[maxn];
int u[maxn];
int n, m, k;

int pos(int x, int y){
    return (x - 1) * m + y;
}

void solve(int x1, int y1, int x2, int y2){
    t[x1][y1] = t[x2][y2] = 1e9;
    for(int i=x1;i<=x2;i++){
        for(int j=y1;j<=y2;j++){
            if(i == x1 && j == y1){
                dp[i][j] = 1e9;
                continue;
            }
            dp[i][j] = -1e9;
            if(i > x1) dp[i][j] = max(dp[i][j], min(dp[i-1][j], t[i][j]));
            if(j > y1) dp[i][j] = max(dp[i][j], min(dp[i][j-1], t[i][j]));
        }
    }
    if(dp[x2][y2] > 1e6) return;
    int y = u[dp[x2][y2]] % m;
    if(y == 0) y += m;
    int x = (u[dp[x2][y2]] - y) / m + 1;
    ans[dp[x2][y2]] = 0;
    solve(x1, y1, x, y);
    solve(x, y, x2, y2);
}

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j];
            t[i][j] = 1e9;
            if(a[i][j]){
                t[i][j] = 0;
            }
        }
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++){
        int x, y;
        cin >> x >> y;
        t[x][y] = i;
        u[i] = pos(x, y);
        ans[i] = 1;
    }
    solve(1, 1, n, m);
    for(int i=1;i<=q;i++){
        cout << ans[i] << ent;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

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