#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){
if(!may[p.ff][p.ss]) continue;
cnt[p.ff + p.ss]--;
stack<pii> st;
st.push({p.ff, p.ss});
may[p.ff][p.ss] = 0;
cnt[p.ff + p.ss]--;
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;
if(!may[i - 1][j + 1]){
if(may[i][j + 1]){
st.push({i, j + 1});
may[i][j + 1] = 0;
cnt[i + j + 1]--;
}
if(may[i - 1][j]){
st.push({i - 1, j});
may[i - 1][j] = 0;
cnt[i + j - 1]--;
}
}
if(!may[i + 1][j - 1]){
if(may[i + 1][j]){
st.push({i + 1, j});
may[i + 1][j] = 0;
cnt[i + j + 1]--;
}
if(may[i][j - 1]){
st.push({i, j - 1});
may[i][j - 1] = 0;
cnt[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, y});
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;
if(!may[i - 1][j + 1]){
if(may[i][j + 1]){
st.push({i, j + 1});
may[i][j + 1] = 0;
cnt[i + j + 1]--;
}
if(may[i - 1][j]){
st.push({i - 1, j});
may[i - 1][j] = 0;
cnt[i + j - 1]--;
}
}
if(!may[i + 1][j - 1]){
if(may[i + 1][j]){
st.push({i + 1, j});
may[i + 1][j] = 0;
cnt[i + j + 1]--;
}
if(may[i][j - 1]){
st.push({i, j - 1});
may[i][j - 1] = 0;
cnt[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 |
2 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 |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
