제출 #1145270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145270		thecrazycandy	Trampoline (info1cup20_trampoline)	C++20	0 / 100	2105 ms	242280 KiB

trampoline

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)2e5 + 1;
map <ll, ll> up[19];
ll n, m, k;
ll fnd (ll v, ll t) {
	for (int bit = 18; bit >= 0; bit--) {
		if (up[bit][v] != 0 && (up[bit][v] - 1) / m < t - 1) v = up[bit][v];
	}
	return v;
}
int main () {
	sped_up;
	cin >> n >> m >> k;
	map <ll, vector <ll>> mp;
	while (k--) {
		ll x, y;
		cin >> x >> y;
		mp[x].push_back(y);
	}
	for (auto i : mp) {
		sort (i.second.begin(), i.second.end());
	}
	for (auto i : mp) {
		ll l = 0;
		for (int j = 0; j < i.second.size(); j++) {
			while (l < mp[i.first + 1].size() && mp[i.first + 1][l] < i.second[j]) j++;
			if (l != mp[i.first + 1].size()) up[0][(i.first - 1) * m + i.second[j]] = i.first * m + mp[i.first + 1][l];
		}
	}
	for (int bit = 1; bit <= 18; bit++) {
		for (auto i : up[bit - 1]) {
			up[bit][i.first] = up[bit - 1][up[bit - 1][i.first]];
		}
	}
	ll q;
	cin >> q;
	while (q--) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2) cout << "Yes\n";
		else {
			ll no = 0;
			for (auto i : mp[x1]) {
				if (y1 <= i) {
					ll f = fnd((x1 - 1) * m + i, x2);
					if (f - (x2 - 2) * m > 0 && f - (x2 - 2) * m <= y2) cout << "Yes\n";
					else cout << "No\n";
					no = 1;
					break;
				}
			}
			if (no == 0) cout << "No\n";
		}
	}
}

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