#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
int n, m;
struct Map{
int x, y;
vector<vector<int>> ref;
vector<bool> ac;
vector<pii> pos_ref;
vector<set<int>> lines;
vector<int> first_lines;
vector<set<int>> cols;
vector<int> first_cols;
vector<pii> neigs(pii pos){
vector<pii> res;
int i= pos.first;
int j = pos.second;
for(int di = -1; di<2; di++){
for(int dj = -1; dj<2; dj++){
if(di!=0|| dj!=0){
if(di+i<x && dj+j<y && di+i>=0 && dj+j>=0){
if(ref[di+i][dj+j]!=-1){
res.push_back(pii(di+i, dj+j));
}
}
}
}
}
return res;
}
vector<pii> spread(pii pos){
int i = pos.first;
int j = pos.second;
vector<pii> r;
auto it = lines[i].lower_bound(j);
if(it != lines[i].begin()){
r.push_back(pii(i, *(--it)));
}
it = cols[j].lower_bound(i);
if(it!=cols[j].begin()){
r.push_back(pii(*(--it), j));
}
if(i+1<x){
it = lines[i+1].lower_bound(j);
if(it != lines[i+1].begin() && lines[i+1].size()>0){
r.push_back(pii( i+1, *(--it)));
}
}
if(j+1<y){
//cout<<"cols "<<j+1<<" "<<cols[j+1].size()<<endl;
it =cols[j+1].lower_bound(i);
if(it !=cols[j+1].begin() && cols[j+1].size()>0){
r.push_back(pii(*(--it), j+1));
}
}
return r;
}
vector<pii> rev_spread(pii pos){
int i = pos.first;
int j = pos.second;
vector<pii> r;
auto it = lines[i].upper_bound(j);
if(it != lines[i].end()){
r.push_back(pii(i,*it));
}
it = cols[j].upper_bound(i);
if(it!=cols[j].end()){
r.push_back(pii(*it, j));
}
if(i-1>=0){
it = lines[i-1].upper_bound(j);
if(it != lines[i-1].end()){
r.push_back(pii(i-1, *(it)));
}
}
if(j-1>=0){
//cout<<"cols "<<j-1<<" "<<cols[j-1].size()<<endl;
it =cols[j-1].upper_bound(i);
if(it !=cols[j-1].end()){
r.push_back(pii(*it, j-1));
}
}
//cout<<"spread size"<<r.size()<<endl;
return r;
}
void dfs(int i, int j){
//cout<<"dfs "<<i<<" "<<j<<endl;
ac[ref[i][j]] = true;
first_cols[j] = max(first_cols[j], i);
first_lines[i] = max(first_lines[i], j);
for(auto e: neigs(pii(i, j))){
if(ref[e.first][e.second]!=-1){
//cout<<e.first<<" "<<e.second<<endl;
//cout<<ref[e.first][e.second]<<endl;
if(!ac[ref[e.first][e.second]]){
//cout<<"here"<<endl;
dfs(e.first, e.second);
}
}
}
//cout<<"none"<<endl;
for(auto e: spread(pii(i, j))){
//cout<<e.first<<" "<<e.second<<endl;
if(!ac[ref[e.first][e.second]]){
dfs(e.first, e.second);
}
}
}
Map(){};
void display(){
}
Map(vector<vector<bool>>& f){
x=f.size()+1;
y = f[0].size()+1;
lines.resize(x);
first_lines.resize(x, -1);
cols.resize(y);
first_cols.resize(y, -1);
ref.resize(x, vector<int> (y, -1));
for(int i = 0; i<x; i++){
for(int j = 0; j<y; j++){
if(i==0|| j==0){
ref[i][j] = ac.size();
ac.push_back(true);
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
}
else{
if(f[i-1][j-1]){
ref[i][j] = ac.size();
ac.push_back(false);
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
}
}
}
}
for(int i = 0; i<ac.size(); i++){
if(ac[i]){
dfs(pos_ref[i].first, pos_ref[i].second);
}
}
display();
}
bool try_insert(pii pos){
int i = pos.first;
int j = pos.second;
bool ok = false;
for(auto e: neigs(pos)){
ok|= ac[ref[e.first][e.second]];
}
ok|=first_lines[i]>=j;
ok|=first_cols[j]>=i;
if(i>0){
ok |=first_lines[i-1]>=j;
}
if(j>0){
ok|= first_cols[j-1]>=i;
}
return ok;
}
void insert(pii pos, bool access){
int i =pos.first;
int j = pos.second;
ref[i][j] = ac.size();
ac.push_back(access);
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
if(ac.back()){
dfs(i, j);
}
}
}maps[2];
vector<vector<bool>> rotate(vector<vector<bool>> a){
vector<vector<bool>> b(a[0].size(), vector<bool>(a.size()));
for(int i = 0; i<a.size(); i++){
for(int j = 0; j<b.size(); j++){
b[j][a.size()-i-1] = a[i][j];
}
}
return b;
}
signed main(){
cin>>n>>m;
vector<vector<bool>> a(n, vector<bool> (m));
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
int c;
cin>>c;
a[i][j] = (c==1);
}
}
auto b = rotate(a);
auto c= rotate(rotate(b));
maps[0]= Map(b);
maps[1] = Map(c);
maps[0].display();
maps[1].display();
int q;
cin>>q;
for(int i = 0; i<q; i++){
int a, b;
cin>>a>>b;
bool ok =maps[0].try_insert(pii(b, n-a+1));
bool ok2= maps[1].try_insert(pii(m-b+1, a));
if(ok && ok2){
cout<<0<<endl;
}
else{
cout<<1<<endl;
maps[0].insert(pii(b, n-a+1), ok);
maps[1].insert(pii(m-b+1, a), ok2);
}
}
}
Compilation message
furniture.cpp: In constructor 'Map::Map(std::vector<std::vector<bool> >&)':
furniture.cpp:160:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i = 0; i<ac.size(); i++){
| ~^~~~~~~~~~
furniture.cpp: In function 'std::vector<std::vector<bool> > rotate(std::vector<std::vector<bool> >)':
furniture.cpp:209:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | for(int i = 0; i<a.size(); i++){
| ~^~~~~~~~~
furniture.cpp:210:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for(int j = 0; j<b.size(); j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1332 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
25 ms |
2544 KB |
Output is correct |
| 5 |
Correct |
27 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
31 ms |
2784 KB |
Output is correct |
| 7 |
Correct |
28 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
27 ms |
2756 KB |
Output is correct |
| 9 |
Correct |
27 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1332 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
25 ms |
2544 KB |
Output is correct |
| 5 |
Correct |
27 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
31 ms |
2784 KB |
Output is correct |
| 7 |
Correct |
28 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
27 ms |
2756 KB |
Output is correct |
| 9 |
Correct |
27 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
88 ms |
8392 KB |
Output is correct |
| 11 |
Correct |
18 ms |
2060 KB |
Output is correct |
| 12 |
Correct |
2214 ms |
92916 KB |
Output is correct |
| 13 |
Correct |
277 ms |
42024 KB |
Output is correct |
| 14 |
Execution timed out |
5085 ms |
184236 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
