oj.uz

Submission #920991

# Submission time Handle Problem Language Result Execution time Memory
920991 2024-02-03T08:42:36 Z yhkhoo Trampoline (info1cup20_trampoline) C++17
0 / 100
 166 ms 35284 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef pair<int, int> pii;

const int MAXN = 200000;
const int INF = 2e9;

int twok[MAXN][20];

int kpar(int x, int k){
	for(int i=0; i<19; i++){
		if(k & (i<<i)) x = twok[x][i];
		if(x == -1) return -1;
	}
	return x;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int X, Y, n;
	cin >> X >> Y >> n;
	pii gt[n];
	for(int i=0; i<n; i++){
		cin >> gt[i].fi >> gt[i].se;
		/*gt[i].fi--;
		gt[i].se--;*/
	}
	sort(gt, gt+n);
	for(int i=0; i<n; i++){
		int nx = lower_bound(gt, gt+n, make_pair(gt[i].fi+1, gt[i].se)) - gt;
		if(nx != n && gt[nx].fi == gt[i].fi+1){
			twok[i][0] = nx;
		}
		else{
			twok[i][0] = -1;
		}
	}
	for(int k=1; k<19; k++){
		for(int i=0; i<n; i++){
			twok[i][k] = twok[twok[i][k-1]][k-1];
		}
	}
	int t;
	cin >> t;
	while(t--){
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 > x2 || y1 > y2){
			cout << "No\n";
			continue;
		}
		if(x1 == x2){
			cout << "Yes\n";
			continue;
		}
		if(x2 - x1 > n){
			cout << "No\n";
			continue;
		}
		int cg = lower_bound(gt, gt+n, make_pair(x1, y1)) - gt;
		if(gt[cg].fi != x1){
			cout << "No\n";
			continue;
		}
		int ym;
		if(x2 - x1 == 1){
			ym = cg;
		}
		else{
			ym = kpar(cg, x2-x1-2);
		}
		if(ym == -1){
			cout << "No\n";
		}
		else if(gt[ym].se <= y2){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

Subtask #1
0 / 23.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 18256 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 166 ms 18336 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 166 ms 18256 KB 200000 token(s): yes count is 86232, no count is 113768
4 Runtime error 90 ms 35284 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2652 KB expected NO, found YES [59th token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 35284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -