Submission #1151128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151128		asdasd	Trampoline (info1cup20_trampoline)	C++20	100 / 100	452 ms	46488 KiB

trampoline

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define tm (tl+tr)/2
#define TL v+v, tl, tm
#define TR v+v+1, tm+1, tr
#define DA l <= tl && tr <= r
#define NE r < tl || tr < l
#define double long double
// #define int long long
using namespace std;

const int N=2e5+7;
const int mod=998244353;
const int inf=2e9;

int r, c, n, q, timer;
map<int,int>mp;
set<pii>st[N];
int up[20][N];
vector<pii>v;

void solve(){
	v.pb({0,0});
	cin >> r >> c >> n;
	for(int i=1; i <= n; i++){
		int a, b;
		cin >> a >> b;
		int x = mp[a];
		if(!x)mp[a]=++timer, x=timer;
		st[x].insert({b, i});
		v.pb({a, b});
	}
	for(int i=1; i <= n; i++){
		int m = mp[v[i].F+1];
		if(m == 0)up[0][i] = -1;
		else{
			auto it = st[m].lower_bound({v[i].S, 0});
			if(it==st[m].end())up[0][i] = -1;
			else up[0][i] = it->S;
		}
	}
	for(int i=1; i < 20; i++){
		for(int j=1; j <= n; j++){
			if(up[i-1][j]==-1)up[i][j]=-1;
			else up[i][j] = up[i-1][up[i-1][j]];
		}
	}
	cin >> q;
	while(q--){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(1 <= x1 && x1 <= r && 1 <= x2 && x2 <= r && 1 <= y1 && y1 <= c && 1 <= y2 && y2 <= c);
		else{
			cout << "No\n";
			continue;
		}
		if(x1==x2){
			if(y1 <= y2)cout << "Yes\n";
			else cout << "No\n";
		}
		else if(x1 > x2)cout << "No\n";
		else{
			int m=mp[x1];
			if(!m){
				cout << "No\n";
				continue;
			}
			auto it = st[m].lower_bound({y1, 0});
			if(it == st[m].end()){
				cout << "No\n";
				continue;
			}
			int cur = it->S;
			int d=x2-x1-1;
			for(int i=0; i < 20; i++){
				if((1<<i)&d)cur = up[i][cur];
				if(cur==-1)break;
			}
			if(cur==-1 || y2 < v[cur].S ){
				cout << "No\n";
			}
			else cout << "Yes\n";
		}
	}
}
signed main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int asd=1;
	// cin >> asd;

	while(asd--)
		solve();
	
return 0;
}

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