Submission #1145306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145306		Muhammet	Trampoline (info1cup20_trampoline)	C++20	100 / 100	1322 ms	68452 KiB

trampoline

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first

const int N = 2e5 + 5;

int c, r, n, x[N], y[N], sp[N][25];

map <int,int> mp;

map <pair<int,int>, int> ind;

map <int, pair<int,int>> ind1;

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

	cin >> r >> c >> n;
	vector <int> v;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];
		ind[{x[i], y[i]}] = i;
		ind1[i] = {x[i], y[i]};
		if(mp.find(x[i]) == mp.end()){
			mp[x[i]] = 1;
			v.push_back(x[i]);
		}
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < SZ(v); i++){
		mp[v[i]] = i;
	}
	vector <vector <int>> v1;
	v1.resize(SZ(v)+1);
	for(int i = 1; i <= n; i++){
		v1[mp[x[i]]].push_back(y[i]);
	}
	for(int i = 0; i < SZ(v1); i++){
		sort(v1[i].begin(), v1[i].end());
	}
	for(int i = 1; i <= n; i++){
		if(mp.find(x[i]+1) == mp.end()){
			continue;
		}
		int k = lower_bound(v1[mp[x[i]+1]].begin(), v1[mp[x[i]+1]].end(), y[i]) - v1[mp[x[i]+1]].begin();
		if(k == SZ(v1[mp[x[i]+1]])) {
			continue;
		}
		sp[i][0] = ind[{x[i]+1,v1[mp[x[i]+1]][k]}];
	}
	for(int j = 1; j <= 20; j++){
		for(int i = 1; i <= n; i++){
			sp[i][j] = sp[sp[i][j-1]][j-1];
		}
	}
	int t;
	cin >> t;
	while(t--){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 == x2 and y1 <= y2){
			cout << "Yes\n";
			continue;
		}
		if(mp.find(x1) == mp.end()){
			cout << "No\n";
			continue;
		}
		int t1 = lower_bound(v1[mp[x1]].begin(), v1[mp[x1]].end(), y1) - v1[mp[x1]].begin();
		if(t1 == SZ(v1[mp[x1]])){
			cout << "No\n";
			continue;
		}
		int k = ind[{x1,v1[mp[x1]][t1]}];
		for(int i = 20; i >= 0; i--){
			if((sp[k][i] > 0)){
				if((x[sp[k][i]] < x2)) k = sp[k][i];
			}
		}

		cout << (x[k] == x2-1 and y[k] <= y2 ? "Yes\n" : "No\n");
	}
}

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