/*====================*\
| |
| written by Franuch |
| |
\*====================*/
/* \/ *\
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&&&&#&#&&&&&&&&&&&&#####B#####BBBBBB######&&&&&&&&@&&&@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&##&&&&&&&&&&&&&&&&######BBBBBBBB#########&&&&&&&&&@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&@&&@@@@@@@@&##&#########BBBGGGGGGGBBBBB##############&&@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&@@@@@@@@@@@@@@@@@@@&#BBBBBBBBGGGGGGGGGGGBBBBBBBBBBBB#####&&@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#BGPGGGGGGGGGGGGGGGGGBGBBBBBBB######&&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&@@@@@@@@@@@@@#BPPPPPPPPPGGGGGGGGGBBBBBBBBBB#####&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&BG5YJ?777?J5G#&@@@@@&&@#GPPPPPPPPPGGGGGGGBBBBBBBBBB#####&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&G5J!~^^^^::::::^^~7JPB&@@@@@@@#GPPP5PPPGGGGGGGGGGBBBBBBBBB##&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@G?~^^::::::::::.....:^^~7?5G#@@@@@&G55P55PPGGGGGGGGGBBBBBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@G!.::::::::^^::.... ...:^~!7?JYP#@@@&G55PPPPPGGGGGGGGGBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@?..:::::::::::..... ...:^^!7JYYPB&@@@B55PPPPGGGGGGGGGGBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&! .::^^^^:::::............::^~!?YPGB#&@@@@#PPPPPGGGBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@J.:::^~!!!~~^^^::::...::..::~7?Y5PG#&@@@@@@@#GPGGGGBBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@B~^^^^~!7!!!~^^:......:!^::^^^~!7?J5G#&&@@@@@@#GGGGBBBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@5~~~~!7!!!!7777!7?7~~.:7:.:^^:^7YPG#&@@@@@@@@@@BGGGGBB####BBBBBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@5?7?JJ??Y5GGB#&&@@&##Y??. .~?!J#@@@@@@@@@@@@@@@@BGGGBB#######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@&5555Y5G&@@@@@@@@@@@@@@#?. ^YG&@@@@@@@@@@@@@@@@@&GPGGBB######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@BPGGB#@@@@@@@@@@&&@&@&&B?:..^Y@@@@@@@@@@@@@@@@@@@@BPPGBBBBB####BBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@&GGB&@@@@@@@&##&@&#B#&@#BY~^^7G@@@@@@@@@@@@@@@@@@@@#PPGGBBB#B###BBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@BPG#&@@@@&#BGGB#&@@B5P#&B57^!5&@@@@@@@@@@@@@@@@@@@@&PPGBB######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@&PPGB&@@@@&@@@@@@@YG@BYGGP5?~!5@@@@@@@@@@@@@@@@@@@@@&BPGGB######BBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@#55G#@@@@@@@@@@@@@?Y@@PJYPPJ!!Y&@@@@@@@@@@@@@@@@@@@@@#PPGBBB###BBBBBBBBB##
@@@@@@@@@@@@@@@@@@@@@@@@@@PY5PG#&&&&&&&#&&&&&@@&BYPPPY!~?#@@@@@@@@@@@@@@@@@@@@@@GPGGBBBBBBBBBBBBBB##
@@@@@@@@@@@@@@@@@&PJ??B@@&YY5P555PPGBB#&&&###G5JJY55P5?~7B@@@@@@@@@@@@@@@@@@@@@@#PGGGGBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@5B#B5B@@#Y555J7!!777?????7!~~!7?J5PP5?!~5@@@@@@@@@@@@@@@@@@@@@@@BGGGGGBBBBBBBBBB###
@@@@@@@@@@@@@@@@5B@&YY&@@G555Y7~^^::^^~~~!!7?YPGGB#B5J?7!?B@@@@@@@@@@@@@@@@@@@@@@&GGGGGBBBBBBBBB####
@@@@@@@@@@@@@@@#Y@&!~P@&#PGP5J!^:...:^^~7J5G##&P?7YGJ!~~JJY#@@@@@@@@@@@@@@@@@@@@@@BGGGGGBBB#######&#
@@@@@@@@@@@@@@@&J&J!#@P^GPGGPJ!^:..^!7?5B&@&GYGBGPG#BGPB&&&@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB########&&
@@@@@@@@@@@@@@@@PJ?5@@5!PPPP5J7~~~~!?YB@@&GYJJ5B&&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB###&##&&&&
@@@@@@@@@@@@@@@@@JJ?55BPPP5P5JJJY?7?YB@&GYJJ??JJJJ5PGB#&@@@@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB#&&&&&&@@&
@@@@@@@@@@@@@@@@@G^!~:~PPP555Y55YYJYG@#5YYJ?7!~~~~!!7JYPPGB#&@@@@@@@@@@@@@@@@@@@@@BGGGGGB#&&&&&&@@@@
@@@@@@@@@@@@@@@@@&PJJ?Y#P555YJ55YYYJG&Y?5PY7~~~~~!!7?YYYY5GB#&&@@@@@@@@@@@@@@@@@@@BGGGGGB#&&@@&&@@@@
@@@@@@@@@@@@@@@@@@@@@&@BP55YYJYPYY?75GJ5G&#BB###BBBB##&@@@@@@@@@@@@@@@@@@@@@@@@@@@BGGGGGB##&@@@&@@@@
@@@@@@@@@@@@@@@@@@@@@B#G555YY??YJ?7^:7?Y5Y7??77!~^~~~~!?JJY5PG#@@@@@@@@@@@@@@@@@@@&GGGGGBB#&@@&&@@@@
@@@@@@@@@@@@@@@@@@@@&G#GPPP5Y?7JJ?7^.:!!^.. .....:^~!?JJY5PB#@@@@@@@@@@@@@@@@@@@@GGGGGBB#&@&&@@@@@
@@@@@@@@@@@@@@@@@@@@#P#GPPPP5J7??JJ!^^~~:.. ...:..:^~!7J5555GB#&&@@@@@@@@@@@@@@@@@@#GGGGBB#&&&&&&@@@
@@@@@@@@@@@@@@@@@@@@BP##GGPP5J??7?Y?!~~^:.........:^~!7?JJJJ5PGB&&&@@@@@@@@@@@@@@@@&BGGGBB##&&&&&&@@
@@@@@@@@@@@@@@@@@@@@BP#&#BGP5YJ?77?J7~::::...:....:^!77??YJJ5PG####&@@@@@@@@@@@@@@@&BGGGBBB#####&&@@
@@@@@@@@@@@@@@@@@@@@BG@@&#BGPYJ??77?7~:::::..::.....::^^~!!7JYPPPPB#@@@@@@@@@@@@@@@@BGGGGBBB####&&@@
@@@@@@@@@@@@@@@@@@@&BB@&@&#BPYJ???77?!~::........ .....:^^~!?JJJY5G#@@@@@@@@@@@@@@@@#GGGBBBBBB##&&@@
@@@@@@@@@@@@@@@@@@@&BG&&&&##GPYJJ?????7!^::......:::...:^^~!?JJY5G#&@@@@@@@@@@@@@@@@&GGGGGBBBBBB#&&@
@@@@@@@@@@@@@@@@@@@&#B#&#&&##BP5YYJJYYYYJ7~~~~~~~^~!^:^~~!7?J5PPB&@@@@@@@@@@@@@@@@@@@#GGGGGBBBBB##&&
@@@@@@@@@@@@@@@@@@@@#BB&&#&&&&#GP555555GGGYJJ??JJ77????J5P5YPB##@@@@@@@@@@@@@@@@@@@@@@BGGGBBBBBBB#&&
@@@@@@@@@@@@@@#GBB#@&BGB&@&&@@&&#BGGGPGB#&&BGGGGGGGBBB##&&##@@@@@@@@@@@@@@@@@@@@@@@@@@@#BBBBBBBB##&&
@@@@@@@@@@@@@#?!YGB##BGGG#@@&@@@@@&&&&#&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&#BBB####&&@
@@@@@@@@@@@@@G!~~?PGGBBGGPG#@@&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##&&&&&&@
@@@@@@@@@@@@@@G7~~!YGGGGGGGGB&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@&&&&&&&@#5~^^75GGGBB###&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&@@@@
\* /\ */
//\\//\\//\\//\\//\\//\\//\\//\\//\\// utils and macros //\\//\\//\\//\\//\\//\\//\\//\\//\\//
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
#define vc vector
#define st first
#define nd second
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define pub push_back
#define pob pop_back
void program();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
program();
return 0;
}
ll INF = 1e18;
vc<ll> P9 = {998'244'353, 1'000'000'007, 1'000'000'009, 1'000'000'021, 1'000'000'033, 1'000'000'087, 1'000'000'093};
ll MOD = P9[0];
bool cont(ll mask, ll i) {
return (mask & (1ll << i)) != 0;
}
ll msb(ll mask) {
if (mask == 0)
return -1;
return 63 - __builtin_clzll(mask);
}
ll ceil(ll a, ll b) {
return (a + b - 1) / b;
}
ll f(ll x) {
x %= MOD;
if (x < 0)
x += MOD;
return x;
}
ll fme(ll a, ll b) {
ll ret = 1, x = a;
while (b > 0) {
if (b % 2 == 1)
ret = f(ret * x);
x = f(x * x);
b /= 2;
}
return ret;
}
ll inv(ll x) {
return fme(x, MOD - 2);
}
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// solution //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
vc<pll> off = {{-1, -1}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1}};
void program() {
ll n, m;
cin >> n >> m;
vc<vc<bool>> a(n + 2, vc<bool>(m + 2, false));
auto l = a, r = a;
for (ll j = 2; j < m + 2; j++)
r[0][j] = true;
for (ll i = 1; i < n; i++)
r[i][m + 1] = true;
for (ll i = 2; i < n + 2; i++)
l[i][0] = true;
for (ll j = 1; j < m; j++)
l[n + 1][j] = true;
function<void(ll, ll)> dfs1 = [&](ll i, ll j) {
if (i < 1 or n < i or j < 1 or m < j or l[i][j])
return;
l[i][j] = true;
for (pll &p : off) {
ll x = i + p.st, y = j + p.nd;
if (a[x][y])
dfs1(x, y);
}
dfs1(i + 1, j);
dfs1(i, j - 1);
};
function<void(ll, ll)> dfs2 = [&](ll i, ll j) {
if (i < 1 or n < i or j < 1 or m < j or r[i][j])
return;
r[i][j] = true;
for (pll &p : off) {
ll x = i + p.st, y = j + p.nd;
if (a[x][y])
dfs2(x, y);
}
dfs2(i, j + 1);
dfs2(i - 1, j);
};
function<bool(ll, ll)> update = [&](ll i, ll j) {
ll s = 0;
for (pll &p : off) {
ll x = i + p.st, y = j + p.nd;
if (l[x][y])
s |= 1;
if (r[x][y])
s |= 2;
}
if (s == 3)
return false;
a[i][j] = true;
if (s == 1)
dfs1(i, j);
else if (s == 2)
dfs2(i, j);
return true;
};
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++) {
ll s;
cin >> s;
if (s)
update(i, j);
}
ll q;
cin >> q;
while (q--) {
ll i, j;
cin >> i >> j;
cout << update(i, j) << "\n";
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
