Submission #692264

#	Time	Username	Problem	Language	Result	Execution time	Memory
692264		NeroZein	Trampoline (info1cup20_trampoline)	C++14	0 / 100	2063 ms	91240 KiB

trampoline

/*
 *    author: NeroZein
 *    created: 01.02.2023 11:11:00
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int r, c, t;
	cin >> r >> c >> t;
	map<int, set<pair<int,int>>> mp; 
	vector<pair<int,int>> p(t); 
	for (int i = 0; i < t; ++i) {
		cin >> p[i].first >> p[i].second; 
	}
	sort(p.begin(), p.end()); 
	for (int i = 0; i < t; ++i) {
		mp[p[i].first].insert({p[i].second, i});
	}
	const int Log = 20; 
	vector<vector<int>> dp(100005, vector<int>(Log)); 
	for (int i = 0; i < t; ++i) {
		auto se = mp[p[i].first-1]; 
		auto it = se.upper_bound(make_pair(p[i].second, 1e9)); 
		if (se.empty() || it == se.begin()) {
			dp[i][0] = -1; 
		}
		else {
			--it;
			dp[i][0] = it->second;
		}
	}
	for (int j = 1; j < Log; ++j) {
		for (int i = 0; i < t; ++i) {
			if (dp[i][j-1] == -1) {
				continue; 
			}
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
	auto jump = [&](int u, int k) {
		for (int i = 0; i < Log; ++i) {
			if ((k >> i) & 1) {
				u = dp[u][i];
				if (u == -1) {
					break; 
				}
			}
		}
		return u; 
	};
	int q;
	cin >> q; 
	while(q--) {
		int xs, ys, xf, yf;
		cin >> xs >> ys >> xf >> yf; 
		if (xs > xf || ys > yf) {
			cout << "NO\n";
			continue; 
		}
		if (xs == xf) {
			cout << "YES" << '\n';
			continue; 
		}
		auto se = mp[xf-1];
		if (se.empty()) {
			cout << "NO" << '\n';
			continue; 
		}
		auto it = se.upper_bound(make_pair(xf, yf));
		if (it == se.begin()) {
			cout << "NO" << '\n';
			continue;
		}
		--it; 
		xf = it->first, xs = it->second;
		int k = xf - xs; 
		int pp = jump(xf, k); 
		cout << (pp == -1 ? "NO\n" : (p[pp].second < ys ? "NO\n" : "YES\n"));
	}
	return 0;
}

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