Submission #921040

#	Time	Username	Problem	Language	Result	Execution time	Memory
921040		yhkhoo	Trampoline (info1cup20_trampoline)	C++17	100 / 100	309 ms	24220 KiB

trampoline

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

#define fi first
#define se second

typedef pair<int, int> pii;

const int MAXN = 200005;
const int INF = 2e9;

int twok[MAXN][19];

int kpar(int x, int k){
	for(int i=0; i<19; i++){
		if(x == -1) return -1;
		if(k & (1<<i)) x = twok[x][i];
	}
	return x;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int X, Y, n;
	cin >> X >> Y >> n;
	pii gt[n];
	for(int i=0; i<n; i++){
		cin >> gt[i].fi >> gt[i].se;
		/*gt[i].fi--;
		gt[i].se--;*/
	}
	sort(gt, gt+n);
	for(int i=0; i<n; i++){
		int nx = lower_bound(gt, gt+n, make_pair(gt[i].fi+1, gt[i].se)) - gt;
		if(nx != n && gt[nx].fi == gt[i].fi+1){
			twok[i][0] = nx;
		}
		else{
			twok[i][0] = -1;
		}
		//cout << twok[i][0] << ' ';
	}
	//cout << '\n';
	for(int k=1; k<19; k++){
		for(int i=0; i<n; i++){
			if(twok[i][k-1] == -1){
				twok[i][k] = -1;
			}
			else{
				twok[i][k] = twok[twok[i][k-1]][k-1];
			}
			//cout << twok[i][k] << ' ';
		}
		//cout << '\n';
	}
	int t;
	cin >> t;
	while(t--){
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 > x2 || y1 > y2){
			cout << "No\n";
			continue;
		}
		if(x1 == x2){
			cout << "Yes\n";
			continue;
		}
		if(x2 - x1 > n){
			cout << "No\n";
			continue;
		}
		int cg = lower_bound(gt, gt+n, make_pair(x1, y1)) - gt;
		if(cg == n || gt[cg].fi != x1){
			cout << "No\n";
			continue;
		}
		int ym = kpar(cg, x2-x1-1);
		if(ym == -1){
			cout << "No\n";
		}
		else if(gt[ym].se <= y2){
			//cout << cg << ' ' << ym << ' ';
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

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