#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define x first
#define y second
typedef long long ll;
const int maxn = 2e6 + 1;
ll func(pair<int, int> a) {
return ((ll)a.x << 30) | a.y;
}
char mat[1001][1001];
vector<int> g[maxn / 2];
vector<int> gr[maxn / 2];
unordered_map<ll, int> num;
int beg[maxn];
int t[maxn * 4];
int pos[maxn];
int a[maxn];
char in[maxn], out[maxn];
bool used[maxn], pus[maxn];
int n, m, uk;
int to(int x, int y) {
return m * x + y;
}
vector<int> path;
int susp[maxn * 3];
int head = 0, tail = 0;
void dfs(int v) {
pus[v] = 1;
for (int u : g[v])
if (!pus[u])
dfs(u);
path.push_back(v);
}
void build(int v, int l, int r) {
if (l == r - 1) {
t[v] = a[l];
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int getmax(int v, int l, int r, int l2, int r2) {
if (l == l2 && r == r2)
return t[v];
int m = (l + r) / 2;
if (r2 <= m)
return getmax(v * 2, l, m, l2, r2);
if (l2 >= m)
return getmax(v * 2 + 1, m, r, l2, r2);
return max(getmax(v * 2, l, m, l2, m), getmax(v * 2 + 1, m, r, m, r2));
}
void upd(int v, int l, int r, int pos) {
if (l == r - 1) {
t[v] = -1;
return;
}
int m = (l + r) / 2;
if (pos >= m)
upd(v * 2 + 1, m, r, pos);
else
upd(v * 2, l, m, pos);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void de(int v) {
used[v] = 1;
for (int u : g[v]) {
upd(1, 0, uk, num[func({v, u})]);
if (!used[u]) {
in[u]--;
if (in[u] == 0)
susp[tail++] = u;
}
}
for (int u : gr[v]) {
upd(1, 0, uk, num[func({u, v})]);
if (!used[u]) {
out[u]--;
if (out[u] == 0)
susp[tail++] = u;
}
}
}
void clr() {
while (head != tail) {
if (!used[susp[head]])
de(susp[head++]);
else
head++;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
g[i].reserve(2);
gr[i].reserve(2);
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
if (mat[i][j] == '1')
used[to(i, j)] = 1;
}
}
for (int i = 1; i < n; i++)
for (int j = 0; j < m; j++)
if (mat[i][j] != '1' && mat[i - 1][j] != '1') {
g[to(i - 1, j)].push_back(to(i, j));
gr[to(i, j)].push_back(to(i - 1, j));
in[to(i, j)]++;
out[to(i - 1, j)]++;
}
for (int i = 0; i < n; i++)
for (int j = 1; j < m; j++)
if (mat[i][j] != '1' && mat[i][j - 1] != '1') {
g[to(i, j - 1)].push_back(to(i, j));
gr[to(i, j)].push_back(to(i, j - 1));
in[to(i, j)]++;
out[to(i, j - 1)]++;
}
used[0] = 1;
int fn = m * (n - 1) + m - 1;
used[fn] = 1;
for (int i = 1; i < fn; i++) {
if ((in[i] == 0 || out[i] == 0)) {
susp[tail++] = i;
}
}
for (int i = 0; i <= fn; i++)
if (!pus[i])
dfs(i);
reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); i++)
pos[path[i]] = i;
for (int i = 0; i < path.size(); i++) {
beg[path[i]] = uk;
for (auto el : g[path[i]]) {
num[func({path[i], el})] = uk;
a[uk++] = pos[el];
}
}
build(1, 0, uk);
clr();
int q;
cin >> q;
/*
for (auto el : rin)
cout << '\t' << el.x << ' ' << el.y << endl;
for (int i = 0; i < path.size(); i++)
cout << path[i] << ' ';
cout << endl;
for (int i = 0; i < uk; i++)
cout << a[i] << ' ';
cout << endl;
*/
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
int p = to(x - 1, y - 1);
//cout << beg[p] << endl;
if (!used[p] && getmax(1, 0, uk, 0, beg[p]) <= pos[p]) {
cout << "0\n";
}
else {
cout << "1\n";
if (!used[p]) {
susp[tail++] = p;
clr();
}
}
}
return 0;
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int i = 0; i < path.size(); i++)
| ~~^~~~~~~~~~~~~
furniture.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
48640 KB |
Output is correct |
| 2 |
Correct |
37 ms |
48128 KB |
Output is correct |
| 3 |
Correct |
41 ms |
48760 KB |
Output is correct |
| 4 |
Correct |
44 ms |
49016 KB |
Output is correct |
| 5 |
Correct |
45 ms |
49272 KB |
Output is correct |
| 6 |
Correct |
54 ms |
49656 KB |
Output is correct |
| 7 |
Correct |
47 ms |
49656 KB |
Output is correct |
| 8 |
Correct |
48 ms |
49656 KB |
Output is correct |
| 9 |
Correct |
48 ms |
49656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
48640 KB |
Output is correct |
| 2 |
Correct |
37 ms |
48128 KB |
Output is correct |
| 3 |
Correct |
41 ms |
48760 KB |
Output is correct |
| 4 |
Correct |
44 ms |
49016 KB |
Output is correct |
| 5 |
Correct |
45 ms |
49272 KB |
Output is correct |
| 6 |
Correct |
54 ms |
49656 KB |
Output is correct |
| 7 |
Correct |
47 ms |
49656 KB |
Output is correct |
| 8 |
Correct |
48 ms |
49656 KB |
Output is correct |
| 9 |
Correct |
48 ms |
49656 KB |
Output is correct |
| 10 |
Correct |
121 ms |
56984 KB |
Output is correct |
| 11 |
Correct |
47 ms |
49408 KB |
Output is correct |
| 12 |
Correct |
2350 ms |
215364 KB |
Output is correct |
| 13 |
Correct |
1274 ms |
191320 KB |
Output is correct |
| 14 |
Correct |
2534 ms |
209064 KB |
Output is correct |
| 15 |
Correct |
2672 ms |
212728 KB |
Output is correct |
| 16 |
Correct |
2573 ms |
232276 KB |
Output is correct |
| 17 |
Correct |
2890 ms |
240504 KB |
Output is correct |
| 18 |
Correct |
2993 ms |
236624 KB |
Output is correct |
| 19 |
Correct |
2745 ms |
245944 KB |
Output is correct |
| 20 |
Correct |
2863 ms |
245804 KB |
Output is correct |
| 21 |
Correct |
2744 ms |
245800 KB |
Output is correct |
