oj.uz

Submission #962223

# Submission time Handle Problem Language Result Execution time Memory
962223 2024-04-13T09:14:17 Z 0npata Furniture (JOI20_furniture) C++17
100 / 100
 1918 ms 114024 KB 
#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define pb push_back
#define pi pair<int, int>
#define fst first
#define snd second



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vec<vec<int>> g(n, vec<int>(m));

	for(int i = 0; i<n; i++) {
		for(int j = 0; j<m; j++) {
			cin >> g[i][j];
		}
	}



	set<pi> fc;
	set<pi> fr;

	vec<vec<bool>> vis(n, vec<bool>(m));
	vec<vec<int>> ok(n, vec<int>(m));

	vis[0][0] = true;

	for(int i = 0; i<n; i++) {
		for(int j = 0; j < m; j++) {
			if(i==0 && j == 0) continue;
			if(g[i][j]) continue;
			bool res = false;
			if(j > 0) res |= vis[i][j-1];
			if(i > 0) res |= vis[i-1][j];
			vis[i][j] = res;
		}
	}

	ok[n-1][m-1] = true;
	for(int i = n-1; i>=0; i--) {
		for(int j = m-1; j>=0; j--) {
			if(i==n-1 && j==m-1) continue;
			if(g[i][j]) continue;
			bool res = false;
			if(j < m-1) res |= ok[i][j+1];
			if(i < n-1) res |= ok[i+1][j];
			ok[i][j] = res & vis[i][j];

			if(ok[i][j]) {
				fc.insert({i, j});
				fr.insert({j, i});
			}
		}
	}




	int q;
	cin >> q;
	while(q--) {
		int r, c;
		cin >> r >> c;
		r--;c--;

		// check whether is a critical point
		int cp = true;
		auto lbcol_it = fc.lower_bound({r+1, 0});
		if(lbcol_it != fc.end()) {
			pi lbcol = *lbcol_it;
			int lbr = lbcol.fst;
			int lbc = lbcol.snd;

			if(lbr == r+1 && lbc < c) {
				cp = false;
			}
		}
		auto rtrow_it = fr.lower_bound({c+1, 0});
		if(rtrow_it != fr.end()) {
			auto rtrow = *rtrow_it;
			int rtc = rtrow.fst;
			int rtr = rtrow.snd;

			if(rtc == c+1 && rtr < r) {
				cp = false;
			}
		}

		if(cp) {
			cout << '0' << '\n';
			continue;
		}

		cout << '1' << '\n';

		auto remove = [&](pi pos) {
			vec<pi> stack{pos};
			while(stack.size() > 0) {
				pi cur = stack.back();
				stack.pop_back();

				int cr = cur.fst;
				int cc = cur.snd;

				fc.erase({cr, cc});
				fr.erase({cc, cr});

				ok[cr][cc] = false;

				// push down
				if(cr < n-1 && ok[cr+1][cc]) {
					// check whether its left is still in tact
					if(cc == 0 || !ok[cr+1][cc-1]) {
						stack.pb({cr+1, cc});
					}
				}
				// push right
				if(cc < m-1 && ok[cr][cc+1]) {
					// check whether its top is still in tact
					if(cr == 0 || !ok[cr-1][cc+1]) {
						stack.pb({cr, cc+1});
					}
				}
			}
		};

		vec<pi> stack{{r, c}};
		while(stack.size() >0) {
			pi cur = stack.back();
			stack.pop_back();
			remove(cur);

			int cr = cur.fst;
			int cc = cur.snd;

			// push up
			if(cr > 0 && ok[cr-1][cc]) {
				// check whether its right is still in tact
				if(cc == m-1 || !ok[cr-1][cc+1]) {
					stack.pb({cr-1, cc});
				}
			}
			// push left
			if(cc > 0 && ok[cr][cc-1]) {
				// check whether its down is still in tact
				if(cr == n-1 || !ok[cr+1][cc-1]) {
					stack.pb({cr, cc-1});
				}
			}
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 10 ms 1116 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 9 ms 1372 KB Output is correct
8 Correct 8 ms 1368 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 10 ms 1116 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 9 ms 1372 KB Output is correct
8 Correct 8 ms 1368 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 14 ms 1428 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 1451 ms 84576 KB Output is correct
13 Correct 504 ms 59188 KB Output is correct
14 Correct 1672 ms 86948 KB Output is correct
15 Correct 1663 ms 96356 KB Output is correct
16 Correct 1457 ms 104432 KB Output is correct
17 Correct 1465 ms 110404 KB Output is correct
18 Correct 1918 ms 107580 KB Output is correct
19 Correct 1368 ms 114024 KB Output is correct
20 Correct 1159 ms 114008 KB Output is correct
21 Correct 1305 ms 113808 KB Output is correct