Submission #306039

#	Time	Username	Problem	Language	Result	Execution time	Memory
306039		TadijaSebez	Furniture (JOI20_furniture)	C++11	100 / 100	3753 ms	28280 KiB

furniture

#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 (stderr)

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){
      |  ^~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95