#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e3 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, c[N][N];
set<int> avail[N << 1];// diagonals (available from (1, 1) and (n, m))
set<int> avail2[N << 1];
void prep(){
avail[n + m].insert(n);
for(int i = n + m - 1; i >= 2; i--){
for(int x = max(1LL, i - m); x <= min(i - 1, n); x++){
int y = i - x;
if(c[x][y] == 1) continue;
if(avail[i + 1].find(x) != avail[i + 1].end() || avail[i + 1].find(x + 1) != avail[i + 1].end()) avail[i].insert(x);
}
}
avail2[2].insert(1);
for(int i = 3; i <= n + m; i++){
for(int x = max(1LL, i - m); x <= min(i - 1, n); x++){
int y = i - x;
if(c[x][y] == 1) continue;
if(avail2[i - 1].find(x) != avail2[i - 1].end() || avail2[i - 1].find(x - 1) != avail2[i - 1].end()){
//cout << x << " " << y << "\n";
avail2[i].insert(x);
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(avail[i + j].find(i) != avail[i + j].end() && avail2[i + j].find(i) == avail2[i + j].end()){
avail[i + j].erase(i);
//cout << i << " " << j << "\n";
}
}
}
//assert(avail[2].size() != 0);
//assert(avail[n + m].size() != 0);
}
set<int> er[N << 1];
bool upd(int x, int y){
if(avail[x + y].find(x) == avail[x + y].end()){
c[x][y] = 1;
return 1;
}
if(avail[x + y].size() == 1) return 0;
er[x + y].clear();
er[x + y].insert(x);
for(int i = x + y; i >= 3; i--){
if(!er[i].size()) break;
er[i - 1].clear();
for(auto tempx : er[i]){
int tempy = i - tempx;
// check {tempx - 1, tempy}
if(avail[i - 1].find(tempx - 1) != avail[i - 1].end() && (er[i].find(tempx - 1) != er[i].end() || avail[i].find(tempx - 1) == avail[i].end())) er[i - 1].insert(tempx - 1);
// check {tempx, tempy - 1}
if(avail[i - 1].find(tempx) != avail[i - 1].end() && (er[i].find(tempx + 1) != er[i].end() || avail[i].find(tempx + 1) == avail[i].end())) er[i - 1].insert(tempx);
}
}
er[x + y].clear();
er[x + y].insert(x);
for(int i = x + y; i < n + m; i++){
if(!er[i].size()) break;
er[i + 1].clear();
for(auto tempx : er[i]){
int tempy = i - tempx;
if(avail[i + 1].find(tempx) != avail[i + 1].end() && (er[i].find(tempx - 1) != er[i].end() || avail[i].find(tempx - 1) == avail[i].end())) er[i + 1].insert(tempx);
if(avail[i + 1].find(tempx + 1) != avail[i + 1].end() && (er[i].find(tempx + 1) != er[i].end() || avail[i].find(tempx + 1) == avail[i].end())) er[i + 1].insert(tempx + 1);
}
}
for(int i = x + y; i >= 2; i--){
if(!er[i].size()) break;
for(auto it : er[i]){
//cout << i << " " << it << "\n";
avail[i].erase(it);
}
}
for(int i = x + y; i <= n + m; i++){
if(!er[i].size()) break;
for(auto it : er[i]){
//cout << i << " " << it << "\n";
avail[i].erase(it);
}
}
assert(avail[2].size());
c[x][y] = 1;
return 1;
}
void process(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++) cin >> c[i][j];
}
prep();
/*
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++) cout << (avail[i + j].find(i) != avail[i + j].end()) << " ";
cout << "\n";
}*/
// return;
int q;
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
cout << upd(x, y) << "\n";
//for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++) cout << (avail[i + j].find(i) != avail[i + j].end()) << " ";
// cout << "\n";
//}
}
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("furniture.inp", "r", stdin);
//freopen("furniture.out", "w", stdout);
process();
}
Compilation message
furniture.cpp: In function 'bool upd(long long int, long long int)':
furniture.cpp:70:8: warning: unused variable 'tempy' [-Wunused-variable]
70 | int tempy = i - tempx;
| ^~~~~
furniture.cpp:83:14: warning: unused variable 'tempy' [-Wunused-variable]
83 | int tempy = i - tempx;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1248 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
19 ms |
1820 KB |
Output is correct |
| 6 |
Correct |
23 ms |
2040 KB |
Output is correct |
| 7 |
Correct |
21 ms |
1996 KB |
Output is correct |
| 8 |
Correct |
21 ms |
2160 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1248 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
19 ms |
1820 KB |
Output is correct |
| 6 |
Correct |
23 ms |
2040 KB |
Output is correct |
| 7 |
Correct |
21 ms |
1996 KB |
Output is correct |
| 8 |
Correct |
21 ms |
2160 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
50 ms |
3444 KB |
Output is correct |
| 11 |
Correct |
22 ms |
1724 KB |
Output is correct |
| 12 |
Correct |
1733 ms |
90228 KB |
Output is correct |
| 13 |
Correct |
549 ms |
69220 KB |
Output is correct |
| 14 |
Correct |
2536 ms |
91320 KB |
Output is correct |
| 15 |
Correct |
2593 ms |
96964 KB |
Output is correct |
| 16 |
Correct |
2299 ms |
105056 KB |
Output is correct |
| 17 |
Correct |
2428 ms |
110692 KB |
Output is correct |
| 18 |
Correct |
2765 ms |
107808 KB |
Output is correct |
| 19 |
Correct |
2346 ms |
114004 KB |
Output is correct |
| 20 |
Correct |
2409 ms |
133052 KB |
Output is correct |
| 21 |
Correct |
2473 ms |
118208 KB |
Output is correct |
