oj.uz

Submission #411492

# Submission time Handle Problem Language Result Execution time Memory
411492 2021-05-25T12:21:10 Z nichke Furniture (JOI20_furniture) C++14
100 / 100
 453 ms 19776 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int n, m, q;

int ar[1005][1005];

void push(stack<pair<int, int>>& st, int x, int y, vector<vector<int>>& val, vector<int>& cnt) {
	if (val[x][y] == 0) {
		val[x][y] = 1;
		--cnt[x + y];
		st.push({x, y});
	}
}

int change(int x, int y, vector<vector<int>>& val, vector<int>& cnt) {
	if (val[x][y] == 1) {
		return 1;
	}
	if (cnt[x + y] == 1) {
		return 0;
	}
	stack<pair<int, int>> st;
	push(st, x, y, val, cnt);
	while (!st.empty()) {
		int x = st.top().first;
		int y = st.top().second;
		st.pop();
		if (val[x - 1][y + 1] == 1) {
			push(st, x - 1, y, val, cnt);
			push(st, x, y + 1, val, cnt);
		}
		if (val[x + 1][y - 1] == 1) {
			push(st, x, y - 1, val, cnt);
			push(st, x + 1, y, val, cnt);
		}
	}
	return 1;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<vector<int>> val(n + 2, vector<int>(m + 2, 1));
	vector<int> cnt(n + m + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			val[i][j] = 0;
			cnt[i + j]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ar[i][j];
			if (ar[i][j] == 1) {
				change(i, j, val, cnt);
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		cout << change(x, y, val, cnt) << '\n';
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 4 ms 756 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 5 ms 848 KB Output is correct
8 Correct 5 ms 772 KB Output is correct
9 Correct 5 ms 772 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 4 ms 756 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 5 ms 848 KB Output is correct
8 Correct 5 ms 772 KB Output is correct
9 Correct 5 ms 772 KB Output is correct
10 Correct 13 ms 1080 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 203 ms 12544 KB Output is correct
13 Correct 85 ms 9292 KB Output is correct
14 Correct 386 ms 17004 KB Output is correct
15 Correct 362 ms 17080 KB Output is correct
16 Correct 364 ms 18256 KB Output is correct
17 Correct 400 ms 19288 KB Output is correct
18 Correct 400 ms 18760 KB Output is correct
19 Correct 453 ms 19772 KB Output is correct
20 Correct 379 ms 19776 KB Output is correct
21 Correct 407 ms 19716 KB Output is correct