#include <bits/stdc++.h>
constexpr int L = 1001, inf = 1001001001;
std::array<std::array<int, L>, L> dp, times;
std::vector<std::pair<int, int>> ps;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::vector<bool>> C(N, std::vector<bool>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
int x;
std::cin >> x;
C[i][j] = (x == 0);
if (C[i][j]) {
times[i][j] = inf;
} else {
times[i][j] = -1;
}
}
}
int Q;
std::cin >> Q;
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
std::cin >> X[i] >> Y[i];
--X[i], --Y[i];
times[X[i]][Y[i]] = i;
}
std::stack<std::pair<std::pair<int, int>, std::pair<int, int>>> stk;
ps.push_back({0, 0});
ps.push_back({N - 1, M - 1});
auto calc = [&](int l1, int r1, int l2, int r2) {
for (int i = l1; i <= r1; ++i) {
for (int j = l2; j <= r2; ++j) {
dp[i][j] = -1;
}
}
dp[l1][l2] = inf;
for (int i = l1; i < r1; ++i) {
for (int j = l2; j < r2; ++j) {
const int m = std::min(dp[i][j], times[i][j + 1]);
dp[i][j + 1] = std::max(dp[i][j + 1], m);
const int m2 = std::min(dp[i][j], times[i + 1][j]);
dp[i + 1][j] = std::max(dp[i + 1][j], m2);
}
}
for (int i = l1; i < r1; ++i) {
const int m = std::min(dp[i][r2], times[i + 1][r2]);
dp[i + 1][r2] = std::max(dp[i + 1][r2], m);
}
for (int i = l2; i < r2; ++i) {
const int m = std::min(dp[r1][i], times[r1][i + 1]);
dp[r1][i + 1] = std::max(dp[r1][i + 1], m);
}
};
stk.push({{0, N - 1}, {0, M - 1}});
calc(0, N - 1, 0, M - 1);
std::vector<int> answer(Q, 1);
while (not stk.empty()) {
const auto t = stk.top();
stk.pop();
const int lx = t.first.first, rx = t.first.second, ly = t.second.first, ry = t.second.second;
if (dp[rx][ry] == inf) continue;
const int x = X[dp[rx][ry]], y = Y[dp[rx][ry]];
times[x][y] = inf;
answer[dp[rx][ry]] = 0;
calc(x, rx, y, ry);
if (x - lx > 1 or y - ly > 1) stk.push({{lx, x}, {ly, y}});
if (rx - x > 1 or ry - y > 1) stk.push({{x, rx}, {y, ry}});
dp[x][y] = -1;
if (x != 0) {
dp[x][y] = std::max(dp[x][y], dp[x - 1][y]);
}
if (y != 0) {
dp[x][y] = std::max(dp[x][y], dp[x][y - 1]);
}
}
for (const auto e : answer) {
std::cout << e << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
