// #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 = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+31;
int n,m,q;
struct Fenwick {
vector<vector<int> > data;
int sz1, sz2;
void reset(int s1, int s2) {
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] %= MOD;
}
}
}
void upd(int x1, int y1, int x2, int y2, int val) {
val %= MOD;
int neg = MOD - 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 %= MOD;
}
}
return ret;
}
};
Fenwick ft1, ft2;
inline void solve() {
cin>>n>>m;
ft1.reset(n + 1, m + 1);
ft2.reset(n + 1, m + 1);
vector<vector<int> > tmp(n + 1, vector<int>(m + 1, 0));
vector<vector<bool> > gr(n + 3, vector<bool>(m + 3, 0));
tmp[0][1] = 1;
for(int i = 1; i<=n; i++) {
for(int j = 1; j <= m; j++) {
bool f;
cin >> f;
gr[i][j] = f;
}
}
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[i][j] += tmp[i - 1][j];
if(!gr[i][j - 1]) tmp[i][j] += tmp[i][j - 1];
tmp[i][j] %= MOD;
ft1.upd(i, j, i, j, tmp[i][j]);
}
}
tmp.assign(n + 3, vector<int>(m + 3, 0));
tmp[n][m + 1] = 1;
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[i][j] += tmp[i + 1][j];
if(!gr[i][j + 1]) tmp[i][j] += tmp[i][j + 1];
tmp[i][j] %= MOD;
ft2.upd(i, j, i, j, tmp[i][j]);
}
}
cin >> q;
for(int i = 1; i<=q; i++) {
int x,y;
cin >> x >> y;
int res = 1ll * ft1.getSum(x, y) * ft2.getSum(x, y);
res %= MOD;
if(res == ft1.getSum(n, m)) {
cout << "0\n";
}
else {
cout << "1\n";
ft1.upd(x, y, n, m, MOD - ft1.getSum(x, y));
ft2.upd(1, 1, x, y, MOD - ft2.getSum(x, y));
}
}
}
signed main() {
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
