oj.uz

Submission #495305

# Submission time Handle Problem Language Result Execution time Memory
495305 2021-12-18T10:23:51 Z 600Mihnea Furniture (JOI20_furniture) C++17
0 / 100
 5000 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int M = 1111111121;


int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

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;
  }
  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;
  }
  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);
      }
    }


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

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 836 KB Output is correct
2 Execution timed out 5076 ms 972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 836 KB Output is correct
2 Execution timed out 5076 ms 972 KB Time limit exceeded
3 Halted 0 ms 0 KB -