#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
void ckmx(int&x,int y){x=max(x,y);}
void ckmn(int&x,int y){x=min(x,y);}
const int N=1050;
const int inf=1e9+7;
int c[N][N],dp1[N][N],dp2[N][N],ans[N*N];
void Solve(int x1,int y1,int x2,int y2,int t){
if(x1==x2&&y1==y2)return;
if(x1==x2){
for(int i=y1+1;i<y2;i++)if(c[x1][i]!=inf)ans[c[x1][i]]=0;
return;
}
if(y1==y2){
for(int i=x1+1;i<x2;i++)if(c[i][y1]!=inf)ans[c[i][y1]]=0;
return;
}
int mx=0,x,y;
if(t==1){
dp1[x1][y1]=inf;
for(int i=x1;i<=x2;++i)for(int j=y1;j<=y2;++j)if(i!=x1||j!=y1){
dp1[i][j]=0;
if(i!=x1)ckmx(dp1[i][j],dp1[i-1][j]);
if(j!=y1)ckmx(dp1[i][j],dp1[i][j-1]);
ckmn(dp1[i][j],c[i][j]);
int now=min(dp1[i][j],dp2[i][j]);
if(now!=c[i][j]||(i==x2&&j==y2))continue;
if(now>mx)mx=now,x=i,y=j;
}
}
if(t==0){
dp2[x2][y2]=inf;
for(int i=x2;i>=x1;--i)for(int j=y2;j>=y1;--j)if(i!=x2||j!=y2){
dp2[i][j]=0;
if(i!=x2)ckmx(dp2[i][j],dp2[i+1][j]);
if(j!=y2)ckmx(dp2[i][j],dp2[i][j+1]);
ckmn(dp2[i][j],c[i][j]);
int now=min(dp1[i][j],dp2[i][j]);
if(now!=c[i][j]||(i==x1&&j==y1))continue;
if(now>mx)mx=now,x=i,y=j;
}
}
if(mx==0||mx==inf)return;
ans[c[x][y]]=0;
c[x][y]=inf;
Solve(x1,y1,x,y,0);
Solve(x,y,x2,y2,1);
}
int main(){
int n,m,q;
scanf("%i %i",&n,&m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
scanf("%i",&c[i][j]);
if(c[i][j])c[i][j]=0;
else c[i][j]=inf;
}
scanf("%i",&q);
for(int i=1,x,y;i<=q;i++){
scanf("%i %i",&x,&y);
c[x][y]=i;
ans[i]=1;
}
dp1[1][1]=inf;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(i!=1||j!=1){
dp1[i][j]=0;
if(i!=1)ckmx(dp1[i][j],dp1[i-1][j]);
if(j!=1)ckmx(dp1[i][j],dp1[i][j-1]);
ckmn(dp1[i][j],c[i][j]);
}
Solve(1,1,n,m,0);
for(int i=1;i<=q;i++)printf("%i\n",ans[i]);
return 0;
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%i %i",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%i",&c[i][j]);
| ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
59 | scanf("%i",&q);
| ~~~~~^~~~~~~~~
furniture.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | scanf("%i %i",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
furniture.cpp: In function 'void Solve(int, int, int, int, int)':
furniture.cpp:16:2: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
16 | if(y1==y2){
| ^~
furniture.cpp:12:2: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
12 | if(x1==x2){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1664 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1664 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1536 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
239 ms |
18296 KB |
Output is correct |
| 13 |
Correct |
109 ms |
14072 KB |
Output is correct |
| 14 |
Correct |
452 ms |
24568 KB |
Output is correct |
| 15 |
Correct |
473 ms |
25080 KB |
Output is correct |
| 16 |
Correct |
3430 ms |
26332 KB |
Output is correct |
| 17 |
Correct |
3753 ms |
27932 KB |
Output is correct |
| 18 |
Correct |
1226 ms |
27260 KB |
Output is correct |
| 19 |
Correct |
504 ms |
28152 KB |
Output is correct |
| 20 |
Correct |
416 ms |
28152 KB |
Output is correct |
| 21 |
Correct |
481 ms |
28280 KB |
Output is correct |
