#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int N, M; cin >> N >> M;
vector< vector<int> > blocked(N, vector<int>(M, 0)), out = blocked, in = blocked;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) {
if (j + 1 < M) {
out[i][j]++;
in[i][j + 1]++;
}
if (i + 1 < N) {
out[i][j]++;
in[i + 1][j]++;
}
}
vector<int> leftmost(N + M, N), rightmost(N + M, 0);
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) {
leftmost[i + j] = min(leftmost[i + j], i);
rightmost[i + j] = max(rightmost[i + j], i);
}
queue< pair<int, int> > Q;
auto block = [&](int x, int y) {
Q.emplace(x, y);
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
if (blocked[x][y])
continue;
blocked[x][y] = 1;
if (x > 0 && --out[x - 1][y] == 0) {
Q.emplace(x - 1, y);
}
if (y > 0 && --out[x][y - 1] == 0) {
Q.emplace(x, y - 1);
}
if (x + 1 < N && --in[x + 1][y] == 0) {
Q.emplace(x + 1, y);
}
if (y + 1 < M && --in[x][y + 1] == 0) {
Q.emplace(x, y + 1);
}
while (leftmost[x + y] == x && blocked[x][y]) {
++leftmost[x + y];
++x;
--y;
}
while (rightmost[x + y] == x && blocked[x][y]) {
--rightmost[x + y];
--x;
++y;
}
}
};
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) {
int x; cin >> x;
if (x == 1)
block(i, j);
}
int K; cin >> K;
while (K--) {
int x, y; cin >> x >> y;
--x; --y;
if (leftmost[x + y] == x && rightmost[x + y] == x) {
cout << 0 << "\n";
continue;
}
cout << 1 << "\n";
block(x, y);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
11 ms |
384 KB |
Output is correct |
4 |
Correct |
20 ms |
512 KB |
Output is correct |
5 |
Correct |
23 ms |
416 KB |
Output is correct |
6 |
Correct |
26 ms |
512 KB |
Output is correct |
7 |
Correct |
26 ms |
512 KB |
Output is correct |
8 |
Correct |
26 ms |
512 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
11 ms |
384 KB |
Output is correct |
4 |
Correct |
20 ms |
512 KB |
Output is correct |
5 |
Correct |
23 ms |
416 KB |
Output is correct |
6 |
Correct |
26 ms |
512 KB |
Output is correct |
7 |
Correct |
26 ms |
512 KB |
Output is correct |
8 |
Correct |
26 ms |
512 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
10 |
Correct |
67 ms |
1024 KB |
Output is correct |
11 |
Correct |
16 ms |
512 KB |
Output is correct |
12 |
Correct |
910 ms |
12124 KB |
Output is correct |
13 |
Correct |
137 ms |
10872 KB |
Output is correct |
14 |
Correct |
2203 ms |
12792 KB |
Output is correct |
15 |
Correct |
2300 ms |
12280 KB |
Output is correct |
16 |
Correct |
2455 ms |
13228 KB |
Output is correct |
17 |
Correct |
2613 ms |
13876 KB |
Output is correct |
18 |
Correct |
2540 ms |
13528 KB |
Output is correct |
19 |
Correct |
2688 ms |
14456 KB |
Output is correct |
20 |
Correct |
2596 ms |
14200 KB |
Output is correct |
21 |
Correct |
2704 ms |
14612 KB |
Output is correct |