Submission #1318518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318518		Jawad_Akbar_JJ	Trampoline (info1cup20_trampoline)	C++20	100 / 100	564 ms	41852 KiB

trampoline

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
const int N = 1<<18;
int Nxt[N][21], x[N], y[N];
map<int, vector<pair<int, int>>> mp;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m,k,q;
	cin>>n>>m>>k;

	vector<pair<int, int>> v1, v2;
	vector<int> v;
	for (int i=1;i<=k;i++){
		cin>>x[i]>>y[i];
		mp[x[i]].push_back({y[i], i});
		v.push_back(x[i]);
	}
	sort(begin(v), end(v));
	v.resize(unique(begin(v), end(v)) - begin(v));

	for (int i : v)
		sort(begin(mp[i]), end(mp[i]));
	
	for (int i : v){
		if (mp[i+1].size() == 0)
			continue;
		v1 = mp[i], v2 = mp[i+1];

		for (auto [y, ind] : v1){
			int u = upper_bound(v2.begin(), v2.end(), make_pair(y, 0)) - begin(v2);
			if (u < v2.size())
				Nxt[ind][0] = v2[u].second;
		}
	}

	for (int j=0;j<20;j++){
		for (int i=1;i<=k;i++)
			Nxt[i][j+1] = Nxt[Nxt[i][j]][j];
	}

	cin>>q;
	for (int i=1;i<=q;i++){
		int x1, x2, y1, y2;
		cin>>x1>>y1>>x2>>y2;

		if (x2 < x1 or y2 < y1){
			cout<<"No\n";
			continue;
		}
		if (x1 == x2){
			cout<<"Yes\n";
			continue;
		}

		int u = upper_bound(begin(mp[x1]), end(mp[x1]), make_pair(y1, 0)) - begin(mp[x1]);
		if (u == mp[x1].size()){
			cout<<"No\n";
			continue;
		}

		int id = mp[x1][u].second, d = x2 - x1 - 1;
		// cout<<id<<" ";

		for (int i=0;i<20;i++){
			if ((1<<i) & d)
				id = Nxt[id][i];//, cout<<i<<'\n';
		}
		// cout<<id<<endl;
		// cout<<y[id]<<" "<<y2<<endl;
		if (id == 0 or y[id] > y2)
			cout<<"No\n";
		else
			cout<<"Yes\n";
	}
}

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