Submission #772586

#TimeUsernameProblemLanguageResultExecution timeMemory
772586gagik_2007Furniture (JOI20_furniture)C++17
0 / 100
251 ms524288 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=1007; const ll LG=25; ll n,m,k; bool a[N][N]; bool bl[N][N]; bool ur[N][N]; bool used[N][N]; set<int>dt[N]; set<int>dc[N]; int urc[N], urt[N]; int blc[N], blt[N]; void kpcruBL(int i, int j){ for(int jj=blt[i]+1;jj<=j;jj++){ a[i][jj]=true; bl[i][jj]=true; } for(int ii=i;ii<blc[j];ii++){ a[ii][j]=true; bl[ii][j]=true; } } void kpcruUR(int i, int j){ for(int jj=j;jj<blt[i];jj++){ a[i][jj]=true; ur[i][jj]=true; } for(int ii=blc[j]+1;ii<=i;ii++){ a[ii][j]=true; ur[ii][j]=true; } } void gnaUR(int i, int j){ kpcruUR(i,j); for(int ii=i-1;ii<=i+1;ii++){ for(int jj=j-1;jj<=j+1;jj++){ if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){ gnaUR(ii,jj); } } } } void gnaBL(int i, int j){ kpcruBL(i,j); for(int ii=i-1;ii<=i+1;ii++){ for(int jj=j-1;jj<=j+1;jj++){ if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){ gnaBL(ii,jj); } } } } int query(int i, int j){ bool urka=false; bool blka=false; for(int ii=i-1;ii<=i+1;ii++){ for(int jj=j-1;jj<=j+1;jj++){ if(a[ii][jj]&&!(ii==i&&jj==j)){ if(ur[ii][jj])urka=true; if(bl[ii][jj])blka=true; } } } if(urka&&blka)return 0; if(urka){ gnaUR(i,j); } if(blka){ gnaBL(i,j); } return 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(i==0||i==n+1||j==0||j==m+1){ a[i][j]=true; if(i==0||j==m+1)ur[i][j]=true; else bl[i][j]=true; continue; } cin>>a[i][j]; if(a[i][j]){ dt[i].insert(j); dc[j].insert(i); } } } urt[0]=0; urc[m+1]=n; for(int i=1;i<=n;i++){ auto it=dt[i].lower_bound(urt[i-1]-1); urt[i]=m+10; if(it!=dt[i].end())urt[i]=*it; for(int j=m;j>=1;j--){ auto itt=dc[j].upper_bound(urc[j+1]+1); urc[j]=-10; if(itt!=dc[j].begin())urc[j]=*(--itt); if(urt[i]<=j||urc[j]>=i){ a[i][j]=true; ur[i][j]=true; dt[i].insert(j); dc[j].insert(i); } } } blt[n+1]=m; blc[0]=0; for(int i=n;i>=1;i--){ auto it=dt[i].upper_bound(blt[i+1]+1); blt[i]=-10; if(it!=dt[i].begin())blt[i]=*(--it); // cout<<"i - "<<i<<": "<<blt[i]<<endl; for(int j=1;j<=m;j++){ // cout<<"dc: "; // for(int x:dc[j]){ // cout<<x<<" "; // } // cout<<endl; auto itt=dc[j].lower_bound(blc[j-1]-1); blc[j]=n+10; if(itt!=dc[j].end())blc[j]=*itt; // cout<<"j - "<<j<<": "<<blc[j]<<endl; if(blt[i]>=j||blc[j]<=i){ a[i][j]=true; // cout<<i<<", "<<j<<": "<<blt[i]<<" "<<blc[j]<<endl; bl[i][j]=true; dt[i].insert(j); dc[j].insert(i); } } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // cout<<a[i][j]<<" "; // } // cout<<endl; // } // cout<<endl; // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // cout<<bl[i][j]<<" "; // } // cout<<endl; // } // cout<<endl; // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // cout<<ur[i][j]<<" "; // } // cout<<endl; // } // cout<<endl; cin>>k; for(int c=0;c<k;c++){ int i,j; cin>>i>>j; cout<<query(i,j)<<endl; // assert(false); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...