Submission #775622

#	Time	Username	Problem	Language	Result	Execution time	Memory
775622		pulsatio	Trampoline (info1cup20_trampoline)	C++14	100 / 100	926 ms	72108 KiB

trampoline

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;

const int MAX = 2e5 + 10;
int r,c,n,t,x[MAX],y[MAX], sp[MAX][30];

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

int up(int a,int b){
	auto it = lower_bound(all(m[a]),b);
	if(it == m[a].end()) return 0;
	return ind[{a,*it}];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> r >> c >> n;

	
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];
		m[x[i]].push_back(y[i]);
		ind[{x[i],y[i]}] = i;
	}


	for(auto &it: m) sort(all(it.second));

	for(int i = 1; i <= n; i++)
		sp[i][0] = up(x[i]+1,y[i]);

	for(int j = 1; j < 30; j++)
		for(int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];	
	cin >> t;
	int x1,y1,x2,y2;
	while(t--){
		cin >> x1 >> y1 >> x2 >> y2;
		
		int d = x2-x1;
		if(x1 > x2 || y1 > y2) cout << "No\n";
		else if(d == 0) cout << "Yes\n";
		else{
			int u = up(x1,y1);
		//	cout << d << endl;
			d--;
			for(int i = 0; i < 30; i++)
				if(d&(1<<i)) u = sp[u][i];
		//	cout << u << endl;
			if(u != 0 && y[u] <= y2)
				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