#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;
}
set<pair<char, int>> rin, rout;
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;
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]) {
rin.erase({ in[u], u });
in[u]--;
rin.insert({ in[u], u });
}
}
for (int u : gr[v]) {
upd(1, 0, uk, num[func({u, v})]);
if (!used[u]) {
rout.erase({ out[u], u });
out[u]--;
rout.insert({ out[u], u });
}
}
}
void clr() {
while (1) {
if (!rin.empty() && rin.begin()->x == 0) {
int v = rin.begin()->y;
rin.erase(rin.begin());
de(v);
continue;
}
if (!rout.empty() && rout.begin()->x == 0) {
int v = rout.begin()->y;
rout.erase(rout.begin());
de(v);
continue;
}
return;
}
}
int fn[maxn];
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 (!used[i]) {
rin.insert({ in[i], i });
rout.insert({ out[i], 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]) {
de(p);
clr();
}
}
}
return 0;
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:183:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | for (int i = 0; i < path.size(); i++)
| ~~^~~~~~~~~~~~~
furniture.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for (int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
49144 KB |
Output is correct |
| 2 |
Correct |
38 ms |
48380 KB |
Output is correct |
| 3 |
Correct |
48 ms |
49408 KB |
Output is correct |
| 4 |
Correct |
55 ms |
49624 KB |
Output is correct |
| 5 |
Correct |
53 ms |
50048 KB |
Output is correct |
| 6 |
Correct |
60 ms |
50356 KB |
Output is correct |
| 7 |
Correct |
54 ms |
50424 KB |
Output is correct |
| 8 |
Correct |
54 ms |
50424 KB |
Output is correct |
| 9 |
Correct |
54 ms |
50424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
49144 KB |
Output is correct |
| 2 |
Correct |
38 ms |
48380 KB |
Output is correct |
| 3 |
Correct |
48 ms |
49408 KB |
Output is correct |
| 4 |
Correct |
55 ms |
49624 KB |
Output is correct |
| 5 |
Correct |
53 ms |
50048 KB |
Output is correct |
| 6 |
Correct |
60 ms |
50356 KB |
Output is correct |
| 7 |
Correct |
54 ms |
50424 KB |
Output is correct |
| 8 |
Correct |
54 ms |
50424 KB |
Output is correct |
| 9 |
Correct |
54 ms |
50424 KB |
Output is correct |
| 10 |
Correct |
162 ms |
60988 KB |
Output is correct |
| 11 |
Correct |
54 ms |
50316 KB |
Output is correct |
| 12 |
Correct |
4551 ms |
294800 KB |
Output is correct |
| 13 |
Correct |
1890 ms |
262948 KB |
Output is correct |
| 14 |
Correct |
4444 ms |
291780 KB |
Output is correct |
| 15 |
Execution timed out |
5078 ms |
296404 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
