oj.uz

Submission #427269

# Submission time Handle Problem Language Result Execution time Memory
427269 2021-06-14T13:52:15 Z model_code Robot Race (CPSPC17_race) C++
100 / 100
 1316 ms 292012 KB 
#include <bitset>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MAXN = 1000;
const int MAXQ = 1000000;

int n, m, q;
bool empty[MAXN][MAXN];
bitset<MAXN> f[MAXN][MAXN], g[MAXN][MAXN];
int sr[MAXQ], sc[MAXQ], tr[MAXQ], tc[MAXQ];
bool ans[MAXQ];

void rec(int from, int to, const vector<int>& remain) {
	if (from > to) return;
	int mid = (from + to) / 2;
	for (int i = mid; i >= from; i--) {
		for (int j = m - 1; j >= 0; j--) {
			f[i][j] = 0;
			if (empty[i][j]) {
				if (i == mid) {
					f[i][j][j] = 1;
				} else {
					f[i][j] |= f[i + 1][j];
				}
				if (j != m - 1) {
					f[i][j] |= f[i][j + 1];
				}
			}
		}
	}
	for (int i = mid; i <= to; i++) {
		for (int j = 0; j < m; j++) {
			g[i][j] = 0;
			if (empty[i][j]) {
				if (i == mid) {
					g[i][j][j] = 1;
				} else {
					g[i][j] |= g[i - 1][j];
				}
				if (j != 0) {
					g[i][j] |= g[i][j - 1];
				}
			}
		}
	}
	vector<int> remain_left, remain_right;
	for (int i : remain) {
		if (tr[i] < mid) {
			remain_left.push_back(i);
		} else if (sr[i] > mid) {
			remain_right.push_back(i);
		} else {
			ans[i] = (f[sr[i]][sc[i]] & g[tr[i]][tc[i]]).any();
		}
	}
	rec(from, mid - 1, remain_left);
	rec(mid + 1, to, remain_right);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	assert(n >= 1 && n <= 1000);
	assert(m >= 1 && m <= 1000);
	assert(q >= 1 && q <= 1000000);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		assert((int) s.length() == m);
		for (int j = 0; j < m; j++) {
			empty[i][j] = s[j] == '.';
		}
	}
	vector<int> remain(q);
	for (int i = 0; i < q; i++) {
		cin >> sr[i] >> sc[i] >> tr[i] >> tc[i];
		assert(sr[i] >= 1 && sr[i] <= n);
		assert(sc[i] >= 1 && sc[i] <= m);
		assert(tr[i] >= 1 && tr[i] <= n);
		assert(tc[i] >= 1 && tc[i] <= m);
		sr[i]--; sc[i]--; tr[i]--; tc[i]--;
		assert(empty[sr[i]][sc[i]]);
		assert(empty[tr[i]][tc[i]]);
		remain[i] = i;
	}
	rec(0, n - 1, remain);
	for (int i = 0; i < q; i++) {
		printf("%s\n", ans[i] ? "YES" : "NO");
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 250740 KB Output is correct
2 Correct 597 ms 249928 KB Output is correct
3 Correct 518 ms 245328 KB Output is correct
4 Correct 476 ms 252056 KB Output is correct
5 Correct 382 ms 248480 KB Output is correct
6 Correct 386 ms 246588 KB Output is correct
7 Correct 586 ms 245508 KB Output is correct
8 Correct 540 ms 245976 KB Output is correct
9 Correct 566 ms 251004 KB Output is correct
10 Correct 522 ms 251776 KB Output is correct
11 Correct 472 ms 249020 KB Output is correct
12 Correct 460 ms 244716 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 250740 KB Output is correct
2 Correct 597 ms 249928 KB Output is correct
3 Correct 518 ms 245328 KB Output is correct
4 Correct 476 ms 252056 KB Output is correct
5 Correct 382 ms 248480 KB Output is correct
6 Correct 386 ms 246588 KB Output is correct
7 Correct 586 ms 245508 KB Output is correct
8 Correct 540 ms 245976 KB Output is correct
9 Correct 566 ms 251004 KB Output is correct
10 Correct 522 ms 251776 KB Output is correct
11 Correct 472 ms 249020 KB Output is correct
12 Correct 460 ms 244716 KB Output is correct
13 Correct 1310 ms 283464 KB Output is correct
14 Correct 1288 ms 282492 KB Output is correct
15 Correct 1249 ms 287800 KB Output is correct
16 Correct 1194 ms 290104 KB Output is correct
17 Correct 1113 ms 285144 KB Output is correct
18 Correct 1166 ms 287008 KB Output is correct
19 Correct 1276 ms 290736 KB Output is correct
20 Correct 1316 ms 292012 KB Output is correct
21 Correct 1252 ms 286376 KB Output is correct
22 Correct 1251 ms 291420 KB Output is correct
23 Correct 1179 ms 287132 KB Output is correct
24 Correct 1172 ms 283736 KB Output is correct