Submission #972230

#	Time	Username	Problem	Language	Result	Execution time	Memory
972230		penguin133	Trampoline (info1cup20_trampoline)	C++17	100 / 100	771 ms	69384 KiB

trampoline

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[20][200005];
int r, c, n, X[200005], Y[200005];
map <int, vector <pi> > mp;

void solve(){
	cin >> r >> c >> n;
	for(int i = 1; i <= n; i++)cin >> X[i] >> Y[i], mp[X[i]].push_back({Y[i], i});
	for(auto &[i, j] : mp){
		sort(j.begin(), j.end());
	}
	for(int i = 1; i <= n; i++){
		pi brr = {Y[i], 0};
		auto tmp = lower_bound(mp[X[i] + 1].begin(), mp[X[i] + 1].end(), brr) - mp[X[i] + 1].begin();
		if(tmp == (int)mp[X[i] + 1].size())par[0][i] = -1;
		else par[0][i] = mp[X[i] + 1][tmp].se;
		//cout << par[0][i] << ' ';
	}
	for(int i = 1; i <= 19; i++){
		for(int j = 1; j <= n; j++){
			if(par[i - 1][j] == -1)par[i][j] = -1;
			else par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	int q; cin >> q;
	while(q--){
		int a, b, c, d; cin >> a >> b >> c >> d;
		
		if(a == c){
			cout << (b <= d ? "Yes\n" : "No\n");
			continue;
		}
		if(c - a - 1 > n || c < a){
			cout << "No\n";
			continue;
		}
		pi brr = {b, 0};
		auto tmp = lower_bound(mp[a].begin(), mp[a].end(), brr) - mp[a].begin();
		if(tmp == (int)mp[a].size()){
			cout << "No\n";
			continue;
		}
		else tmp = mp[a][tmp].se;
		//jump c - a times
		int cur = tmp;
		for(int i = 19; i >= 0; i--){
			if((c - a - 1) >> i & 1)cur = par[i][cur];
			if(cur == -1)break;
		}
		if(cur == -1 || Y[cur] > d){
			cout << "No\n";
		}
		else cout << "Yes\n";
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

trampoline.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

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