#include <bits/stdc++.h>
using namespace std;
struct DisjointSetUnion
{
int rows{}, cols{};
vector<vector<pair<int, int>>> parent;
vector<vector<int>> rank;
vector<vector<int>> colour;
vector<vector<int>> leftmost, topmost;
void init(const int& _rows, const int& _cols)
{
rows = _rows, cols = _cols;
parent.clear(), parent.resize(rows + 2, vector<pair<int, int>>(cols + 2));
rank.clear(), rank.resize(rows + 2, vector<int>(cols + 2, 1));
colour.clear(), colour.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
leftmost.clear(), leftmost.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
topmost.clear(), topmost.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
for (int i = 1; i <= rows; i++)
for (int j = 1; j <= cols; j++)
leftmost[i][j] = j, topmost[i][j] = i;
}
pair<int, int> find(int i, int j)
{
if (parent[i][j].first == 0) return {i, j};
return parent[i][j] = find(parent[i][j].first, parent[i][j].second);
}
void unite(pair<int, int> u, pair<int, int> v)
{
u = find(u.first, u.second), v = find(v.first, v.second);
if (u == v) return;
if (rank[u.first][u.second] > rank[v.first][v.second]) swap(u, v);
rank[v.first][v.second] += rank[u.first][u.second];
parent[u.first][u.second] = v;
colour[v.first][v.second] = min(colour[u.first][u.second], colour[v.first][v.second]);
leftmost[v.first][v.second] = min(leftmost[u.first][u.second], leftmost[v.first][v.second]);
topmost[v.first][v.second] = min(topmost[u.first][u.second], topmost[v.first][v.second]);
}
int getColour(int i, int j)
{
return colour[find(i, j).first][find(i, j).second];
}
void setColour(int i, int j, int c)
{
colour[find(i, j).first][find(i, j).second] = min(c, colour[find(i, j).first][find(i, j).second]);
}
int getLeftmost(int i, int j)
{
return leftmost[find(i, j).first][find(i, j).second];
}
int getTopmost(int i, int j)
{
return topmost[find(i, j).first][find(i, j).second];
}
} dsu;
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};
int rows, cols, queries;
vector<vector<int>> board;
vector<int> colHeight, rowLength;
int main()
{
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin >> rows >> cols;
dsu.init(rows, cols);
board.resize(rows + 2, vector<int>(cols + 2, 1));
for (int i = 1; i <= rows; i++)
for (int j = 1; j <= cols; j++)
cin >> board[i][j];
colHeight.resize(cols + 2);
rowLength.resize(rows + 2);
for (int j = 1, i = 0; j <= cols + 1; j++)
{
dsu.setColour(i, j, 1);
while (i < rows && board[i + 1][j] == 1)
{
dsu.unite({i, j}, {i + 1, j});
i++;
}
colHeight[j] = i;
}
for (int i = 1, j = 0; i <= rows + 1; i++)
{
dsu.setColour(i, j, 2);
while (j < cols && board[i][j + 1] == 1)
{
dsu.unite({i, j}, {i, j + 1});
j++;
}
rowLength[i] = j;
}
for (int i = 1; i <= rows; i++)
for (int j = 1; j <= cols; j++)
if (j > rowLength[i] && i > colHeight[j] && board[i][j] == 1)
{
dsu.setColour(i, j, 3);
for (int d = 0; d < 8; d++)
{
int _x = i + dx[d], _y = j + dy[d];
if (dsu.getColour(_x, _y) == 3)
dsu.unite({i, j}, {_x, _y});
}
}
cin >> queries;
int cnt[4]{};
for (int x, y, q = 1; q <= queries; q++)
{
cin >> x >> y;
cnt[1] = cnt[2] = cnt[3] = 0;
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
if (c != INT_MAX) cnt[c]++;
}
if (!cnt[1] && !cnt[2] && !cnt[3])
{
dsu.setColour(x, y, 3);
cout << "1\n";
continue;
}
if (cnt[1] && !cnt[2] && !cnt[3])
{
dsu.setColour(x, y, 1);
cout << "1\n";
continue;
}
if (!cnt[1] && cnt[2] && !cnt[3])
{
dsu.setColour(x, y, 2);
cout << "1\n";
continue;
}
if (!cnt[1] && !cnt[2] && cnt[3])
{
dsu.setColour(x, y, 3);
cout << "1\n";
continue;
}
if (cnt[1] && cnt[2])
{
cout << "0\n";
continue;
}
if (cnt[1] && cnt[3])
{
int leftmost = INT_MAX;
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
if (c != 3) continue;
leftmost = min(leftmost, dsu.getLeftmost(_x, _y));
}
int i = colHeight[leftmost] + 1;
for (; dsu.getColour(i, leftmost) != 3; i++)
dsu.setColour(i, leftmost, 1);
for (; dsu.getColour(i, leftmost) == 3; i++)
dsu.setColour(i, leftmost, 1);
colHeight[leftmost] = --i;
for (int j = leftmost; j <= cols && i >= colHeight[j]; j++)
{
dsu.setColour(i, j, 1);
while (i < rows && board[i + 1][j] == 1)
{
dsu.unite({i, j}, {i + 1, j});
i++;
}
colHeight[j] = i;
}
cout << "1\n";
continue;
}
if (cnt[2] && cnt[3])
{
int topmost = INT_MAX;
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
if (c != 3) continue;
topmost = min(topmost, dsu.getTopmost(_x, _y));
}
int j = rowLength[topmost] + 1;
for (; dsu.getColour(topmost, j) != 3; j++)
dsu.setColour(topmost, j, 2);
for (; dsu.getColour(topmost, j) == 3; j++)
dsu.setColour(topmost, j, 2);
rowLength[topmost] = --j;
for (int i = topmost; i <= rows && j >= rowLength[i]; i++)
{
dsu.setColour(i, j, 2);
while (j < cols && board[i][j + 1] == 1)
{
dsu.unite({i, j}, {i, j + 1});
j++;
}
rowLength[i] = j;
}
cout << "1\n";
continue;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
