oj.uz

Submission #884599

# Submission time Handle Problem Language Result Execution time Memory
884599 2023-12-07T18:07:19 Z LinkedArray Trampoline (info1cup20_trampoline) C++17
11 / 100
 181 ms 26964 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 25944 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 26076 KB expected YES, found NO [3rd token]
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 26964 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 170 ms 26896 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 175 ms 26852 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 177 ms 26848 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 180 ms 26876 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 172 ms 26964 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 25948 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 26788 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -