| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1227599 | minhpk | Furniture (JOI20_furniture) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int r[1001][1001];
struct cmp{
bool operator()(const pair<int,int> &a,const pair<int,int> &b){
return a.first<b.first;
}
};
set<pair<int,int>,cmp> s[2001];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
for (int i=1;i<=a;i++){
for (int j=1;j<=b;j++){
int x;
cin >> x;
if (x==1){
r[i][j]=1;
}
}
}
for (int i=1;i<=b;i++){
r[a+1][i]=1;
}
for (int i=1;i<=a;i++){
for (int j=1;j<=b;j++){
if (r[i-1][j] && r[i][j-1]){
r[i][j]=1;
}
}
}
for (int i=a;i>=1;i--){
for (int j=b;j>=1;j--){
if (r[i][j+1]&& r[i+1][j]){
r[i][j]=1;
}
}
}
// for (int i=1;i<=a;i++){
// for (int j=1;j<=b;j++){
// cout << r[i][j] << " ";
// }
// cout << "\n";
// }
for (int i=1;i<=a;i++){
for (int j=1;j<=b;j++){
if (r[i][j]==0){
s[i+j].insert({i,j});
}
}
}
int q;
cin >> q;
while (q--){
int x,y;
cin >> x >> y;
if (r[x][y]){
cout << 1 << "\n";
}else{
if (s[x+y].size()>1){
cout << 1 << "\n";
auto it=s[x+y].find({x,y});
s[x+y].erase(it);
r[x][y]=1;
if (r[x+1][y-1] && !r[x+1][y]){
auto it1=s[x+y+1].find({x+1,y});
s[x+y+1].erase(it1);
r[x+1][y]=1;
}
if (r[x-1][y+1] && !r[x][y+1]){
auto it1=s[x+y+1].find({x,y+1});
s[x+y+1].erase(it1);
r[x][y+1]=1;
}
if (r[x+1][y-1] && !r[x][y-1]){
auto it1=s[x+y-1].find({x,y-1});
s[x+y-1].erase(it1);
r[x][y-1]=1;
}
if (r[x-1][y+1] && !r[x-1][y]){
auto it1=s[x+y-1].find({x-1,y});
s[x+y-1].erase(it1);
r[x-1][y]=1;
}
}else{
cout << 0 << "\n";
}
}
}
return 0;
}