제출 #495308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495308		600Mihnea	Furniture (JOI20_furniture)	C++17	100 / 100	351 ms	8752 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1000 + 7;
int cnt[2 * N];
int n, m, a[N][N];
bool ok1[N][N];
bool ok2[N][N];

void compute() {
  ok1[0][1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      ok1[i][j] = (a[i][j] == 0 && (ok1[i - 1][j] || ok1[i][j - 1]));
    }
  }
  ok2[n][m + 1] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      ok2[i][j] = (a[i][j] == 0 && (ok2[i + 1][j] || ok2[i][j + 1]));
      cnt[i + j] += (ok1[i][j] & ok2[i][j]);
    }
  }
}

void reconst1(int i, int j) {
  if ((!(1 <= i && 1 <= j && i <= n && j <= m))) {
    return;
  }
  if (!ok1[i][j]) {
    return;
  }
  bool was = (ok1[i][j] && ok2[i][j]);
  ok1[i][j] = (a[i][j] == 0 && (ok1[i - 1][j] || ok1[i][j - 1]));
  if (!ok1[i][j]) {
    if (was) {
      cnt[i + j]--;
    }
    reconst1(i + 1, j);
    reconst1(i, j + 1);
  }
}

void reconst2(int i, int j) {
  if ((!(1 <= i && 1 <= j && i <= n && j <= m))) {
    return;
  }
  if (!ok2[i][j]) {
    return;
  }
  bool was = (ok1[i][j] && ok2[i][j]);
  ok2[i][j] = (a[i][j] == 0 && (ok2[i + 1][j] || ok2[i][j + 1]));
  if (!ok2[i][j]) {
    if (was) {
      cnt[i + j]--;
    }
    reconst2(i - 1, j);
    reconst2(i, j - 1);
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
    }
  }
  compute();
  int q;
  cin >> q;
  while (q--) {
    int r, c;
    cin >> r >> c;
    if (ok1[r][c] == 0 || ok2[r][c] == 0) {
      a[r][c] = 1;
    } else {
      if (cnt[r + c] >= 2) {
        a[r][c] = 1;
        reconst1(r, c);
        reconst2(r, c);
      }
    }


    cout << a[r][c] << "\n";
  }
}

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