// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e3+5;
const int ALPH = 26;
const int LGN = 25;
const int B = 5;
array<int, B> mods = {(int) 1e9 + 5, (int) 1e9 + 6, (int)1e9 + 7, (int) 1e9 + 8, (int) 1e9 + 9};
int n,m,q;
struct Fenwick {
vector<vector<int> > data;
int md;
int sz1, sz2;
void reset(int ms, int s1, int s2) {
md = ms;
sz1 = s1;
sz2 = s2;
data.assign(s1 + 3, vector<int>(s2 + 3, 0));
}
void change(int x, int y, int val) {
for(; x <= sz1; x += x & (-x)) {
for(int i = y; i <= sz2; i += i & (-i)) {
data[x][i] += val;
data[x][i] %= md;
}
}
}
void upd(int x1, int y1, int x2, int y2, int val) {
val %= md;
int neg = md - val;
change(x1, y1, val);
change(x1, y2 + 1, neg);
change(x2 + 1, y1, neg);
change(x2 + 1, y2 + 1, val);
}
int getSum(int x, int y) {
int ret = 0;
for(; x > 0; x -= x & (-x)) {
for(int i = y; i > 0; i -= i & (-i)) {
ret += data[x][i];
ret %= md;
}
}
return ret;
}
};
Fenwick ft1[B], ft2[B];
inline void solve() {
cin>>n>>m;
REP(b,B) {
ft1[b].reset(mods[b], n + 1, m + 1);
ft2[b].reset(mods[b], n + 1, m + 1);
}
array<vector<vector<int> >, B> tmp;
REP(b,B) {
tmp[b].assign(n + 3, vector<int> (m + 3, 0));
tmp[b][0][1] = 1;
}
vector<vector<bool> > gr(n + 3, vector<bool>(m + 3, 0));
for(int i = 1; i<=n; i++) {
for(int j = 1; j <= m; j++) {
bool f;
cin >> f;
gr[i][j] = f;
}
}
REP(b,B) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(gr[i][j]) continue;
if(!gr[i - 1][j]) tmp[b][i][j] += tmp[b][i - 1][j];
if(!gr[i][j - 1]) tmp[b][i][j] += tmp[b][i][j - 1];
tmp[b][i][j] %= mods[b];
ft1[b].upd(i, j, i, j, tmp[b][i][j]);
}
}
}
REP(b,B) {
tmp[b].assign(n + 3, vector<int> (m + 3, 0));
tmp[b][n][m + 1] = 1;
}
REP(b,B) {
for(int i = n; i >= 1; i--) {
for(int j = m; j >= 1; j--) {
if(gr[i][j]) continue;
if(!gr[i + 1][j]) tmp[b][i][j] += tmp[b][i + 1][j];
if(!gr[i][j + 1]) tmp[b][i][j] += tmp[b][i][j + 1];
tmp[b][i][j] %= mods[b];
ft2[b].upd(i, j, i, j, tmp[b][i][j]);
}
}
}
cin >> q;
for(int i = 1; i<=q; i++) {
int x,y;
cin >> x >> y;
bool f = 1;
REP(b,B) {
int res = 1ll * ft1[b].getSum(x, y) * ft2[b].getSum(x, y);
res %= mods[b];
if(res != ft1[b].getSum(n, m)) f = 0;
}
if(f) {
cout << "0\n";
}
else {
cout << "1\n";
REP(b,B) {
ft1[b].upd(x, y, n, m, mods[b] - ft1[b].getSum(x, y));
ft2[b].upd(1, 1, x, y, mods[b] - ft2[b].getSum(x, y));
}
}
}
}
signed main() {
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
1100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
1100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
