Submission #920991

#	Time	Username	Problem	Language	Result	Execution time	Memory
920991		yhkhoo	Trampoline (info1cup20_trampoline)	C++17	0 / 100	166 ms	35284 KiB

trampoline

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

#define fi first
#define se second

typedef pair<int, int> pii;

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

int twok[MAXN][20];

int kpar(int x, int k){
	for(int i=0; i<19; i++){
		if(k & (i<<i)) x = twok[x][i];
		if(x == -1) return -1;
	}
	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;
		}
	}
	for(int k=1; k<19; k++){
		for(int i=0; i<n; i++){
			twok[i][k] = twok[twok[i][k-1]][k-1];
		}
	}
	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(gt[cg].fi != x1){
			cout << "No\n";
			continue;
		}
		int ym;
		if(x2 - x1 == 1){
			ym = cg;
		}
		else{
			ym = kpar(cg, x2-x1-2);
		}
		if(ym == -1){
			cout << "No\n";
		}
		else if(gt[ym].se <= y2){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

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