#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30;
const ll MAXN = 1100;
int path[MAXN][MAXN];
int cnt[2*MAXN], N, M;
void deactivate(int row, int col) {
path[row][col] = 0;
cnt[row+col]--;
if (row - 1 >= 1 && path[row-1][col] && path[row-1][col+1] == 0)
deactivate(row-1, col);
if (col - 1 >= 1 && path[row][col-1] && path[row+1][col-1] == 0)
deactivate(row, col-1);
if (row + 1 <= N && path[row+1][col] && path[row+1][col-1] == 0)
deactivate(row+1, col);
if (col + 1 <= M && path[row][col+1] && path[row-1][col+1] == 0)
deactivate(row, col+1);
}
bool add(int row, int col) {
if (cnt[row+col] == 1 && path[row][col])
return false;
if (path[row][col] == 0)
return true;
deactivate(row, col);
return true;
}
int main() {
fast
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
path[i][j] = true;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
cnt[i+j]++;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
int x; cin >> x;
if (x)
add(i, j);
}
}
int Q;
cin >> Q;
while (Q--) {
int row, col;
cin >> row >> col;
if (add(row, col))
cout << "1\n";
else
cout << "0\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
2652 KB |
Output is correct |
6 |
Correct |
2 ms |
2652 KB |
Output is correct |
7 |
Correct |
2 ms |
2652 KB |
Output is correct |
8 |
Correct |
2 ms |
2768 KB |
Output is correct |
9 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
2652 KB |
Output is correct |
6 |
Correct |
2 ms |
2652 KB |
Output is correct |
7 |
Correct |
2 ms |
2652 KB |
Output is correct |
8 |
Correct |
2 ms |
2768 KB |
Output is correct |
9 |
Correct |
2 ms |
2652 KB |
Output is correct |
10 |
Correct |
6 ms |
2908 KB |
Output is correct |
11 |
Correct |
2 ms |
2648 KB |
Output is correct |
12 |
Correct |
83 ms |
9236 KB |
Output is correct |
13 |
Correct |
38 ms |
6488 KB |
Output is correct |
14 |
Correct |
137 ms |
14528 KB |
Output is correct |
15 |
Correct |
146 ms |
14484 KB |
Output is correct |
16 |
Correct |
151 ms |
15352 KB |
Output is correct |
17 |
Correct |
155 ms |
16012 KB |
Output is correct |
18 |
Correct |
163 ms |
15524 KB |
Output is correct |
19 |
Correct |
180 ms |
16248 KB |
Output is correct |
20 |
Correct |
163 ms |
16632 KB |
Output is correct |
21 |
Correct |
168 ms |
16212 KB |
Output is correct |