Submission #1145297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145297		stdfloat	Trampoline (info1cup20_trampoline)	C++20	100 / 100	745 ms	48164 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define all(v)  v.begin(), v.end()

#define ff	first
#define ss	second
#define pii	pair<int, int>

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int R, C, n;
	cin >> R >> C >> n;

	vector<int> x(n), y(n);
	map<int, vector<pii>> m;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];

		m[x[i]].push_back({y[i], i});
	}

	for (auto &i : m)
		sort(all(i.second));

	vector<vector<int>> sp(n, vector<int>(20, -1));
	for (auto i : m) {
		if (m.find(i.ff + 1) == m.end()) continue;

		for (auto j : i.ss) {
			auto t = lower_bound(all(m[i.ff + 1]), pii{j.ff, 0});
			if (t != m[i.ff + 1].end()) sp[j.ss][0] = (*t).ss;
		}
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++)
			if (~sp[j][i - 1]) sp[j][i] = sp[sp[j][i - 1]][i - 1];
	}

	int T;
	cin >> T;
	while (T--) {
		int sx, sy, tx, ty;
		cin >> sx >> sy >> tx >> ty;

		int dis = tx - sx - 1;
		if (sx > tx || sy > ty || n < dis) {
			cout << "No\n"; continue;
		}
		if (sx == tx) {
			cout << "Yes\n"; continue;
		}
		if (m.find(sx) == m.end() || m[sx].back().ff < sy) {
			cout << "No\n"; continue;
		}

		int cur = (*lower_bound(all(m[sx]), pii{sy, 0})).ss;
		for (int i = 19; i >= 0 && ~cur; i--)
			if ((dis >> i) & 1) cur = sp[cur][i];

		cout << (~cur && x[cur] + 1 == tx && y[cur] <= ty ? "Yes" : "No") << '\n';
	}
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27