Submission #1254152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254152		sinatbtfard	Furniture (JOI20_furniture)	C++20	100 / 100	117 ms	3444 KiB

furniture

#include <bits/stdc++.h>

#define int long long
#define make_pair mp

using namespace std;

const int maxn = 1e3 + 10;

int n, m, qu, res[maxn + maxn];
bool mark[maxn][maxn];
queue <pair <int, int>> q;

void ins (int x, int y){
	mark[x][y] = 1;
	res[x + y]--;
	q.push({x, y});
}

void update (int sx, int sy){
	ins(sx, sy);
	while (q.size()){
		auto [x, y] = q.front();
		q.pop();
		if (mark[x - 1][y + 1]){
			if (!mark[x - 1][y])
				ins(x - 1, y);
			if (!mark[x][y + 1])
				ins(x, y + 1);
		}
		if (mark[x + 1][y - 1]){
			if (!mark[x + 1][y])
				ins(x + 1, y);
			if (!mark[x][y - 1])
				ins(x, y - 1);
		}
	}
}

void read (){
	cin >> n >> m;
	for (int i = 0; i <= n + 1; i++) mark[i][0] = mark[i][m + 1] = 1;
	for (int j = 0; j <= m + 1; j++) mark[0][j] = mark[n + 1][j] = 1;
	for (int i = 1; i <= n; i++){
		for (int x, j = 1; j <= m; j++){
			cin >> x;
			if (x && !mark[i][j])
				update(i, j);
			res[i + j]++;
		}
	}
}

void solve (){
	cin >> qu;
	while (qu--){
		int x, y; cin >> x >> y;
		if (mark[x][y])
			cout << "1\n";
		else if (res[x + y] == 1)
			cout << "0\n";
		else{
			cout << "1\n";
			update(x, y);
		}
	}
}

int32_t main (){
	ios_base::sync_with_stdio(0), cin.tie(0);
	read();
	solve();
}

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