oj.uz

Submission #495307

# Submission time Handle Problem Language Result Execution time Memory
495307 2021-12-18T10:26:16 Z 600Mihnea Furniture (JOI20_furniture) C++17
100 / 100
 629 ms 28516 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1000 + 7;
vector<pair<int, int>> d[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]));
    }
  }
}

void reconst1(int i, int j) {
  if ((!(1 <= i && 1 <= j && i <= n && j <= m))) {
    return;
  }
  if (!ok1[i][j]) {
    return;
  }
  ok1[i][j] = (a[i][j] == 0 && (ok1[i - 1][j] || ok1[i][j - 1]));
  if (!ok1[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;
  }
  ok2[i][j] = (a[i][j] == 0 && (ok2[i + 1][j] || ok2[i][j + 1]));
  if (!ok2[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];
      d[i + j].push_back({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 {
      assert(ok1[r][c] == 1);
      assert(ok2[r][c] == 1);
      int pos = r + c, cnt = 0;
      for (auto &it : d[pos]) {
        int x = it.first, y = it.second;
        if (ok1[x][y] && ok2[x][y]) {
          cnt++;
        }
      }
      assert(cnt >= 1);
      if (cnt >= 2) {
        a[r][c] = 1;
        reconst1(r, c);
        reconst2(r, c);
      }
    }


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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 3 ms 1012 KB Output is correct
4 Correct 4 ms 1100 KB Output is correct
5 Correct 3 ms 1056 KB Output is correct
6 Correct 4 ms 1164 KB Output is correct
7 Correct 5 ms 1128 KB Output is correct
8 Correct 4 ms 1176 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 3 ms 1012 KB Output is correct
4 Correct 4 ms 1100 KB Output is correct
5 Correct 3 ms 1056 KB Output is correct
6 Correct 4 ms 1164 KB Output is correct
7 Correct 5 ms 1128 KB Output is correct
8 Correct 4 ms 1176 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 8 ms 1464 KB Output is correct
11 Correct 3 ms 840 KB Output is correct
12 Correct 489 ms 20012 KB Output is correct
13 Correct 93 ms 17384 KB Output is correct
14 Correct 599 ms 25236 KB Output is correct
15 Correct 610 ms 24944 KB Output is correct
16 Correct 326 ms 26756 KB Output is correct
17 Correct 324 ms 28004 KB Output is correct
18 Correct 629 ms 27144 KB Output is correct
19 Correct 354 ms 28516 KB Output is correct
20 Correct 285 ms 28488 KB Output is correct
21 Correct 368 ms 28428 KB Output is correct