#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(er[i].find(x - 1) != er[i].end() || avail[i].find(x - 1) == avail[i].end()) er[i - 1].insert(tempx - 1);
// check {tempx, tempy - 1}
if(er[i].find(x + 1) != er[i].end() || avail[i].find(x + 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(er[i].find(x - 1) != er[i].end() || avail[i].find(x - 1) != avail[i].end()) er[i + 1].insert(tempx);
if(er[i].find(x + 1) != er[i].end() || avail[i].find(x + 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]) 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);
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;
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
1740 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
1540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
1740 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
1540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
