/*====================*\
| |
| 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 //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
void program() {
ll n, m;
cin >> n >> m;
vc<vc<ll>> a(n + 1, vc<ll>(m + 1));
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++)
cin >> a[i][j];
function<bool()> dyn = [&]() {
vc<vc<ll>> dp(n + 1, vc<ll>(m + 1, 0));
dp[1][1] = 1;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++) {
if (i == 1 and j == 1)
continue;
if (a[i][j])
continue;
dp[i][j] = dp[i - 1][j] or dp[i][j - 1];
}
return dp[n][m];
};
ll q;
cin >> q;
while (q--) {
ll i, j;
cin >> i >> j;
a[i][j] = 1;
if (dyn())
cout << "1\n";
else {
cout << "0\n";
a[i][j] = 0;
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
