oj.uz

Submission #313709

# Submission time Handle Problem Language Result Execution time Memory
313709 2020-10-16T19:31:02 Z Temmie Furniture (JOI20_furniture) C++17
100 / 100
 416 ms 24032 KB 
#include <bits/stdc++.h>

void place(int X, int Y, std::queue <std::pair <int, int>>& q, std::vector <int>& le, std::vector <int>& ri, std::vector <std::vector <int>>& g, std::vector <std::vector <int>>& ou, std::vector <std::vector <int>>& in, int n, int m) {
	q.push({ X, Y });
	while (q.size()) {
		auto p = q.front(); q.pop();
		int x = p.first, y = p.second;
		if (g[x][y]) continue;
		g[x][y] = 1;
		if (x && !--ou[x - 1][y]) q.push({ x - 1, y });
		if (y && !--ou[x][y - 1]) q.push({ x, y - 1 });
		if (x + 1 < n && !--in[x + 1][y]) q.push({ x + 1, y });
		if (y + 1 < m && !--in[x][y + 1]) q.push({ x, y + 1 });
		while (le[x + y] == x && g[x][y]) le[x + y]++, x++, y--;
		while (ri[x + y] == x && g[x][y]) ri[x + y]--, x--, y++;
	}
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	int n, m; std::cin >> n >> m;
	std::vector <std::vector <int>> g(n, std::vector <int> (m)), ou(g), in(g);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (j + 1 < m) ou[i][j]++, in[i][j + 1]++;
			if (i + 1 < n) ou[i][j]++, in[i + 1][j]++;
		}
	}
	std::vector <int> le(n + m, n), ri(n + m, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			le[i + j] = std::min(le[i + j], i);
			ri[i + j] = std::max(ri[i + j], i);
		}
	}
	std::queue <std::pair <int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int p; std::cin >> p;
			if (p) place(i, j, q, le, ri, g, ou, in, n, m);
		}
	}
	int k; std::cin >> k;
	while (k--) {
		int x, y; std::cin >> x >> y; x--, y--;
		if (le[x + y] == x && ri[x + y] == x) {
			std::cout << "0\n"; continue;
		}
		std::cout << "1\n";
		place(x, y, q, le, ri, g, ou, in, n, m);
	}
	
}





























































































// >_>

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 13 ms 1280 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 258 ms 16120 KB Output is correct
13 Correct 103 ms 12664 KB Output is correct
14 Correct 387 ms 20344 KB Output is correct
15 Correct 379 ms 20216 KB Output is correct
16 Correct 384 ms 21880 KB Output is correct
17 Correct 392 ms 23032 KB Output is correct
18 Correct 389 ms 22392 KB Output is correct
19 Correct 412 ms 23800 KB Output is correct
20 Correct 351 ms 23928 KB Output is correct
21 Correct 416 ms 24032 KB Output is correct