/**
* author: wxhtzdy
* created: 03.08.2022 13:12:41
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
vector<vector<bool>> dp(n, vector<bool>(m));
dp[n - 1][m - 1] = true;
auto Update = [&](int i, int j) {
if (a[i][j] == 1) {
dp[i][j] = false;
return;
}
dp[i][j] = false;
if (i == n - 1 && j == m - 1) {
dp[i][j] = true;
}
if (i + 1 < n) {
dp[i][j] = dp[i][j] | dp[i + 1][j];
}
if (j + 1 < m) {
dp[i][j] = dp[i][j] | dp[i][j + 1];
}
};
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
Update(i, j);
}
}
vector<vector<vector<int>>> id(2, vector<vector<int>>(n, vector<int>(m, -1)));
vector<vector<int>> path(2);
{ // right
int T = 0;
vector<int> que(1, 0);
for (int b = 0; b < (int) que.size(); b++) {
int x = que[b] / m;
int y = que[b] % m;
id[0][x][y] = T++;
if (y < m - 1 && dp[x][y + 1]) {
que.push_back(x * m + y + 1);
} else if (x < n - 1) {
que.push_back((x + 1) * m + y);
}
}
path[0] = que;
}
{ // down
int T = 0;
vector<int> que(1, 0);
for (int b = 0; b < (int) que.size(); b++) {
int x = que[b] / m;
int y = que[b] % m;
id[1][x][y] = T++;
if (x < n - 1 && dp[x + 1][y]) {
que.push_back((x + 1) * m + y);
} else if (y < m - 1) {
que.push_back(x * m + y + 1);
}
}
path[1] = que;
}
auto Go0 = [&](int sx, int sy) {
int T = id[0][sx][sy];
for (int b = T; b < (int) path[0].size(); b++) {
int x = path[0][b] / m;
int y = path[0][b] % m;
id[0][x][y] = b;
if (y + 1 < m && dp[x][y + 1]) {
path[0].push_back(x * m + y + 1);
} else if (x + 1 < n) {
path[0].push_back((x + 1) * m + y);
}
}
};
auto Go1 = [&](int sx, int sy) {
int T = id[1][sx][sy];
for (int b = T; b < (int) path[1].size(); b++) {
int x = path[1][b] / m;
int y = path[1][b] % m;
id[1][x][y] = b;
if (x + 1 < n && dp[x + 1][y]) {
path[1].push_back((x + 1) * m + y);
} else if (y + 1 < m) {
path[1].push_back(x * m + y + 1);
}
}
};
function<void(int, int, bool)> Go = [&](int x, int y, bool fir) {
for (int i = x; i >= 0; i--) {
for (int j = y; j >= 0; j--) {
Update(i, j);
}
}
};
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
bool f0 = (id[0][x][y] == -1);
bool f1 = (id[1][x][y] == -1);
if (f0 && f1) {
cout << 1 << '\n';
dp[x][y] = false;
Go(x, y, true);
a[x][y] = 1;
continue;
}
if (!f0 & !f1) {
cout << 0 << '\n';
continue;
}
cout << 1 << '\n';
a[x][y] = 1;
dp[x][y] = false;
Go(x, y, true);
assert(dp[0][0]);
if (!f0) {
int nx = path[0][id[0][x][y] - 1] / m;
int ny = path[0][id[0][x][y] - 1] % m;
while (path[0].back() != nx * m + ny) {
id[0][path[0].back() / m][path[0].back() % m] = -1;
path[0].pop_back();
}
while (!dp[path[0].back() / m][path[0].back() % m]) {
id[0][path[0].back() / m][path[0].back() % m] = -1;
path[0].pop_back();
}
nx = path[0].back() / m;
ny = path[0].back() % m;
Go0(nx, ny);
}
if (!f1) {
int nx = path[1][id[1][x][y] - 1] / m;
int ny = path[1][id[1][x][y] - 1] % m;
while (path[1].back() != nx * m + ny) {
id[1][path[1].back() / m][path[1].back() % m] = -1;
path[1].pop_back();
}
while (!dp[path[1].back() / m][path[1].back() % m]) {
id[1][path[1].back() / m][path[1].back() % m] = -1;
path[1].pop_back();
}
nx = path[1].back() / m;
ny = path[1].back() % m;
Go1(nx, ny);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
32 ms |
656 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
32 ms |
656 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
