Submission #1123217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123217		Pwo	Trampoline (info1cup20_trampoline)	C++17	100 / 100	547 ms	75936 KiB

trampoline

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

int r, c, n;
set<int> dis;
pair<int, int> a[200005];
vector<int> v;
unordered_map<int, int> mp;
set<pair<int, int>> st[200005];
int down[200005][19];

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> r >> c >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		dis.insert(a[i].first);
	}
	v.assign(dis.begin(), dis.end());
	for (int i = 0; i < v.size(); i++)
		mp[v[i]] = i;
	for (int i = 0; i < n; i++) {
		a[i].first = mp[a[i].first];
		st[a[i].first].insert({a[i].second, i});
	}
		
	for (int i = 0; i < n; i++) {
		auto it = st[a[i].first + 1].lower_bound({a[i].second, 0});
		if (it == st[a[i].first + 1].end()) {
			down[i][0] = -1;
		} else down[i][0] = (*it).second;
	}
	
	for (int k = 1; k <= 18; k++) {
		for (int i = 0; i < n; i++) {
			if (a[i].first + (1 << k) > v.size()
				|| down[i][k - 1] == -1) {
				down[i][k] = -1;
				continue;
			}
			down[i][k] = down[down[i][k - 1]][k - 1];
		}
	}
	
	int t; cin >> t;
	while (t--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2 && y2 >= y1) {
			cout << "Yes\n";
			continue;
		}
		if (x2 < x1 || y2 < y1 ||
		 mp.find(x1) == mp.end() || mp.find(x2 - 1) == mp.end()) {
			cout << "No\n";
			continue;
		}
		
		x1 = mp[x1], x2 = mp[x2 - 1];
		auto it = st[x1].lower_bound({y1, 0});
		if (it == st[x1].end()) { cout << "No\n"; continue; }
		int cur = (*it).second;
		if (a[cur].second > y2) { cout << "No\n"; continue; }
		
		int diff = x2 - x1;
		bool b = 1;
		for (int i = 18; i >= 0; i--) {
			if (diff & (1 << i)) {
				cur = down[cur][i];
				if (cur == -1 || a[cur].second > y2) {
					b = 0;
					break;
				}
			}
		}

		cout << (b ? "Yes\n" : "No\n");
	}
}

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