oj.uz

Submission #891598

# Submission time Handle Problem Language Result Execution time Memory
891598 2023-12-23T10:05:37 Z amirhoseinfar1385 Furniture (JOI20_furniture) C++17
100 / 100
 661 ms 75092 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int dpb[maxn][maxn],dpp[maxn][maxn],dp[maxn][maxn],all[maxn][maxn],n,m;
set<pair<int,int>>st[maxn*3];

void updb(int i,int j){
	if(dpb[i][j]==0){
		return ;
	}
	dpb[i][j]=(dpb[i-1][j]|dpb[i][j-1]);
	if(dpb[i][j]==0){
		st[i+j].erase(make_pair(i,j));
		updb(i+1,j);
		updb(i,j+1);
	}
}

void updp(int i,int j){
	if(dpp[i][j]==0){
		return ;
	}
	dpp[i][j]=(dpp[i+1][j]|dpp[i][j+1]);
	if(dpp[i][j]==0){
		st[i+j].erase(make_pair(i,j));
		updp(i-1,j);
		updp(i,j-1);
	}
}

void query(){
	int i,j;
	cin>>i>>j;
	if((int)st[i+j].size()!=1||st[i+j].count(make_pair(i,j))==0){
		cout<<1<<"\n";
		dp[i][j]=dpb[i][j]=dpp[i][j]=0;
		updb(i,j+1);
		updb(i+1,j);
		updp(i,j-1);
		updp(i-1,j);
		st[i+j].erase(make_pair(i,j));
	}
	else{
		cout<<0<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>all[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(all[i][j]){
				continue;
			}
			if(i==1&&j==1){
				dpb[i][j]=1;
				continue;
			}
			if((dpb[i-1][j]|dpb[i][j-1])==1){
				dpb[i][j]=1;
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			if(i==n&&j==m){
				dpp[i][j]=1;
				continue;
			}
			if(all[i][j]){
				continue;
			}
			if((dpp[i+1][j]|dpp[i][j+1])==1){
				dpp[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=(dpp[i][j]&dpb[i][j]);
			if(dp[i][j]){
				st[i+j].insert(make_pair(i,j));
			}
		}
	}
	int q;
	cin>>q;
	for(int asd=0;asd<q;asd++){
		query();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 4 ms 11352 KB Output is correct
5 Correct 6 ms 11612 KB Output is correct
6 Correct 6 ms 11612 KB Output is correct
7 Correct 5 ms 11612 KB Output is correct
8 Correct 5 ms 11612 KB Output is correct
9 Correct 5 ms 11620 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 4 ms 11352 KB Output is correct
5 Correct 6 ms 11612 KB Output is correct
6 Correct 6 ms 11612 KB Output is correct
7 Correct 5 ms 11612 KB Output is correct
8 Correct 5 ms 11612 KB Output is correct
9 Correct 5 ms 11620 KB Output is correct
10 Correct 9 ms 11324 KB Output is correct
11 Correct 4 ms 11352 KB Output is correct
12 Correct 516 ms 57108 KB Output is correct
13 Correct 159 ms 42976 KB Output is correct
14 Correct 661 ms 60548 KB Output is correct
15 Correct 624 ms 65672 KB Output is correct
16 Correct 462 ms 69972 KB Output is correct
17 Correct 489 ms 73040 KB Output is correct
18 Correct 617 ms 71504 KB Output is correct
19 Correct 493 ms 74984 KB Output is correct
20 Correct 463 ms 74984 KB Output is correct
21 Correct 496 ms 75092 KB Output is correct