Submission #1144953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144953		Halym2007	Trampoline (info1cup20_trampoline)	C++17	30 / 100	105 ms	2696 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
pii p[N];
int n, m, k, q;

//map <int, int> m1, m2;
	
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= k; ++i) {
		cin >> p[i].ff >> p[i].ss;
	}
	sort (p + 1, p + k + 1);
//	for (int i = 1; i <= k; ++i) {
//		if (m1.find (p[i].ff) == m1.end()) {
//			m1[p[i].ff] = i;
//		}
//		m2[p[i].ff] = i;
//	}
	cin >> q;
	if (max (k, q) <= 5000) {
		while ( q-- ) {
			int x, y, x1, y1;
			cin >> x >> y >> x1 >> y1;
			if (x1 < x or y1 < y) {
				cout << "No\n";
				continue;
			}
			if (x1 - x > k) {
				cout << "No\n";
				continue;
			}
			// when it comes here x1 - x <= k --> it means every time you will go at most k times
			for (int i = 1; i <= k; ++i) {
				if (p[i].ff == x and p[i].ss >= y) {
					x++;
					y = p[i].ss;
				}
				if (x == x1) break;
			}
			if (x == x1 and y <= y1) {
				cout << "Yes\n";
			}
			else cout << "No\n";
		}
	}
	else {
		while ( q-- ) {
			int x, y, x1, y1;
			cin >> x >> y >> x1 >> y1;
			if (x1 < x or y1 < y) {
				cout << "No\n";
				continue;
			}
			if (x1 - x > k) {
				cout << "No\n";
				continue;
			}
			// then I will try to find a green grid range y to y1
			auto tr = lower_bound (p + 1, p + k + 1, make_pair(x, y)) - p;
			if (tr == k + 1 or p[tr].ff != x or p[tr].ss > y1) {
				cout << "No\n";
			}
			else cout << "Yes\n";
			
		}
	}
}

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