#include <bits/stdc++.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <cmath>
#include <assert.h>
#include <ctime>
#include <math.h>
#include <queue>
#include <string>
#include <numeric>
#include <fstream>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <stack>
#include <random>
#include <list>
#include <bitset>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update> ordset;
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-Os")
ll INF = 2e18;
//mt19937 gen(time(0));
ll gcd(ll n, ll m){
while(n != 0 && m != 0){
if(n > m) n %= m;
else m %= n;
}
return n + m;
}
ll lcm(ll n, ll m){
ll nod = gcd(n, m);
return n / nod * m;
}
ll mod = 1e9 + 7;
ll binpow(ll n, ll m){
if(m == 0) return 1;
if(m % 2ll == 1) {
return (binpow(n, m - 1ll) * 1ll * n) % mod;
}
ll b = binpow(n, m / 2);
return (b * 1ll * b) % mod;
}
void solve(){
int n, m;
cin >> n >> m;
vector<vector<bool>> may(n + 2, vector<bool>(m + 2, 0));
vector<int> cnt(10000, 0);
vector<vector<int>> a(n + 2, vector<int>(m + 2));
vector<pii> qq;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
cnt[i + j]++;
may[i][j] = 1;
if(a[i][j] == 1){
qq.push_back({i, j});
}
}
}
reverse(all(qq));
for(pii& p : qq){
cnt[p.ff + p.ss]--;
stack<pii> st;
may[p.ff][p.ss] = 0;
st.push({p.ff - 1, p.ss});
st.push({p.ff, p.ss - 1});
st.push({p.ff + 1, p.ss});
st.push({p.ff, p.ss + 1});
while(st.size()){
int i = st.top().ff, j = st.top().ss;
st.pop();
if(i <= 0 || j <= 0 || i > n || j > m || (j == 1 && i == 1) || (j == m && i == n)) continue;
bool was = 0;
if(!may[i - 1][j] && !may[i][j - 1]){
//cout << i << " " << j << '\n';
may[i][j] = 0;
was = 1;
cnt[i + j]--;
if(may[i + 1][j]) st.push({i + 1, j});
if(may[i][j + 1]) st.push({i, j + 1});
}
if(!may[i + 1][j] && !may[i][j + 1]){
//cout << i << " " << j << '\n';
may[i][j] = 0;
if(!was) cnt[i + j]--;
if(may[i - 1][j]) st.push({i - 1, j});
if(may[i][j - 1]) st.push({i, j - 1});
}
}
}
int q;
cin >> q;
for(int h = 0; h < q; h++){
int x, y;
cin >> x >> y;
if(!may[x][y]) {
cout << 1 << '\n';
continue;
}
if(cnt[x + y] <= 1) {
cout << 0 << '\n';
continue;
}
may[x][y] = 0;
cout << 1 << '\n';
stack<pii> st;
st.push({x - 1, y});
st.push({x, y - 1});
st.push({x + 1, y});
st.push({x, y + 1});
cnt[x + y]--;
while(st.size()){
int i = st.top().ff, j = st.top().ss;
st.pop();
if(i <= 0 || j <= 0 || i > n || j > m || (j == 1 && i == 1) || (j == m && i == n)) continue;
bool was = 0;
if(!may[i - 1][j] && !may[i][j - 1]){
may[i][j] = 0;
was = 1;
cnt[i + j]--;
if(may[i + 1][j]) st.push({i + 1, j});
if(may[i][j + 1]) st.push({i, j + 1});
}
if(!may[i + 1][j] && !may[i][j + 1]){
may[i][j] = 0;
if(!was) cnt[i + j]--;
if(may[i - 1][j]) st.push({i - 1, j});
if(may[i][j - 1]) st.push({i, j - 1});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt;
//cin >> tt;
tt = 1;
while (tt--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
