#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> board;
vector<int> colHeight, rowLength;
struct DisjointSetUnion
{
int rows{}, cols{};
vector<vector<pair<int, int>>> parent;
vector<vector<int>> rank;
vector<vector<int>> colour;
vector<vector<int>> leftmost, topmost, rightmost, bottommost;
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));
rightmost.clear(), rightmost.resize(rows + 2, vector<int>(cols + 2, INT_MIN));
bottommost.clear(), bottommost.resize(rows + 2, vector<int>(cols + 2, INT_MIN));
for (int i = 1; i <= rows; i++)
for (int j = 1; j <= cols; j++)
leftmost[i][j] = rightmost[i][j] = j, topmost[i][j] = bottommost[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);
}
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];
}
int getRightmost(int i, int j)
{
return rightmost[find(i, j).first][find(i, j).second];
}
int getBottommost(int i, int j)
{
return bottommost[find(i, j).first][find(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]);
rightmost[v.first][v.second] = max(rightmost[u.first][u.second], rightmost[v.first][v.second]);
bottommost[v.first][v.second] = max(bottommost[u.first][u.second], bottommost[v.first][v.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;
void printBoard()
{
cout << "! ";
for (int j = 1; j <= cols; j++)
cout << ' ' << colHeight[j];
cout << endl;
for (int i = 0; i <= rows + 1; cout << endl, i++)
{
if (1 <= i && i <= rows)
cout << rowLength[i] << ' ';
else
cout << " ";
for (int j = 0; j <= cols + 1; j++)
{
if (dsu.getColour(i, j) == INT_MAX)
cout << "- ";
else
cout << dsu.getColour(i, j) << ' ';
}
}
cout << endl;
}
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;
if (x <= colHeight[y] || y <= rowLength[x])
{
cout << "1\n";
continue;
}
assert(dsu.getColour(x, y) == INT_MAX);
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])
{
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d];
if (dsu.getColour(_x, _y) == 1)
{
dsu.unite({x, y}, {_x, _y});
break;
}
}
cout << "1\n";
continue;
}
if (!cnt[1] && cnt[2] && !cnt[3])
{
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d];
if (dsu.getColour(_x, _y) == 2)
{
dsu.unite({x, y}, {_x, _y});
break;
}
}
cout << "1\n";
continue;
}
if (!cnt[1] && !cnt[2] && cnt[3])
{
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d];
if (dsu.getColour(_x, _y) == 3)
{
dsu.unite({x, y}, {_x, _y});
break;
}
}
cout << "1\n";
continue;
}
if (cnt[1] && cnt[2])
{
cout << "0\n";
continue;
}
if (cnt[1] && cnt[3])
{
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d];
if (dsu.getColour(_x, _y) == 3)
{
dsu.unite({x, y}, {_x, _y});
}
}
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;
if (_x <= colHeight[_y] || _y <= rowLength[_x]) continue;
int leftmost = dsu.getLeftmost(_x, _y);
int i = colHeight[leftmost] + 1;
for (; dsu.getColour(i, leftmost) != 3; i++)
dsu.unite({i - 1, leftmost}, {i, leftmost});
dsu.unite({i - 1, leftmost}, {i, leftmost});
for (; dsu.getColour(i, leftmost) == 1; i++)
dsu.unite({i - 1, leftmost}, {i, leftmost});
colHeight[leftmost] = --i;
for (int j = leftmost + 1; j <= cols; j++)
{
dsu.unite({i, j - 1}, {i, j});
while (i < rows && dsu.getColour(i + 1, j) == 1)
{
dsu.unite({i, j}, {i + 1, j});
i++;
}
colHeight[j] = max(i, colHeight[j]);
}
}
cout << "1\n";
continue;
}
if (cnt[2] && cnt[3])
{
for (int d = 0; d < 8; d++)
{
int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
if (dsu.getColour(_x, _y) == 3)
{
dsu.unite({x, y}, {_x, _y});
}
}
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;
if (_x <= colHeight[_y] || _y <= rowLength[_x]) continue;
int topmost = dsu.getTopmost(_x, _y);
int j = rowLength[topmost] + 1;
for (; dsu.getColour(topmost, j) != 3; j++)
dsu.unite({topmost, j - 1}, {topmost, j});
dsu.unite({topmost, j - 1}, {topmost, j});
for (; dsu.getColour(topmost, j) == 2; j++)
dsu.unite({topmost, j - 1}, {topmost, j});
rowLength[topmost] = --j;
for (int i = topmost + 1; i <= rows; i++)
{
dsu.unite({i - 1, j}, {i, j});
while (j < cols && dsu.getColour(i, j + 1) == 2)
{
dsu.unite({i, j}, {i, j + 1});
j++;
}
rowLength[i] = max(j, rowLength[i]);
}
}
cout << "1\n";
continue;
}
}
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:289:53: warning: unused variable 'c' [-Wunused-variable]
289 | int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
