Submission #884599

#	Time	Username	Problem	Language	Result	Execution time	Memory
884599		LinkedArray	Trampoline (info1cup20_trampoline)	C++17	11 / 100	181 ms	26964 KiB

trampoline

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

constexpr int MAXN = 2e5;

pair<int, int> green[MAXN + 5];
int depth[MAXN + 5];
vector<vector<int>> up(MAXN + 5, vector<int>(log2(MAXN) + 5));

int binLift (int node, int k, int log) {
	int i;
	
	for (i = 0; i < log; i++) {
		if (k & (1 << i)) {
			node = up[node][i];
		}
	}
	
	return node;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int r, c, n, q, x1, y1, x2, y2, st, dr, mij, log, i, j;
	
	cin >> r >> c >> n;
	for (i = 1; i <= n; i++) {
		cin >> green[i].first >> green[i].second;
	}
	sort(green + 1, green + 1 + n);
	
	log = 0;
	while ((1 << log) <= n) {
		log++;
	}
	
	for (i = 1; i <= n; i++) {
		// binary search
		pair<int, int> target = {green[i].first + 1, green[i].second};
		st = 1, dr = n;
		while (st <= dr) {
			mij = (st + dr) / 2;
			
			if (green[mij] >= target) {
				dr = mij - 1;
			} else {
				st = mij + 1;
			}
		}
		// ans = (dr == n ? 0 : dr + 1);
		
		// -----------
		int ans = (dr == n ? 0 : dr + 1);
		bool found = (green[ans].first == target.first);
		
		if (found) {
			depth[i] = depth[ans] + 1;
			
			up[i][0] = ans;
			for (j = 1; j < log; j++) {
				up[i][j] = up[ up[i][j - 1] ][j - 1];
			}
		}
	}	
	
	
	cin >> q;
	for (i = 1; i <= q; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		
		if (x1 > x2 || y1 > y2) {
			cout << "No\n";
		} else {
			if (x1 == x2) {
				cout << "Yes\n";
			} else {
				// query logic
				
				// binary search
				pair<int, int> target = {x1, y1};
				st = 1, dr = n;
				while (st <= dr) {
					mij = (st + dr) / 2;
					
					if (green[mij] >= target) {
						dr = mij - 1;
					} else {
						st = mij + 1;
					}
				}
				// ans = (dr == n ? 0 : dr + 1);
				
				// -----------
				int ans = (dr == n ? 0 : dr + 1);
				
				if (green[ans].first > x1 || green[ans].second > y2) {
					cout << "No\n";
				} else {
					int linDif = (x2 - x1 - 1);
					
					if (depth[ans] < linDif) {
						cout << "No\n";
					} else {
						int ans_pos = binLift(ans, linDif, log);
						
						if (green[ans_pos].first <= x2 && green[ans_pos].second <= y2) {
							cout << "Yes\n";
						} else {
							cout << "No\n";
						}
					}
				}
			}
		}
	}
	return 0;
}

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