Submission #1145057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145057		Agageldi	Trampoline (info1cup20_trampoline)	C++20	62 / 100	2094 ms	26156 KiB

trampoline

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

#define ll long long
#define N 6000006
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()
#define pii pair<int,int>

ll T, n, a[N], inx, r, c, b[5];
map <int,vector <int>> vis;
vector <int> v;
set <int> s;
map <pair<int,int>,int> vip;

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> r >> c >> n;
	for(int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		vip[{x,y}] = 1;
		s.insert(x);
		vis[x].pb(y);
	}
	for(auto i:s) {
		v.pb(i);
	}
	cin >> T;
	for(int i = 1; i <= T; i++) {
		int x, y, w, f;
		cin >> x >> y >> w >> f;
		if(x > w || y > f) {
			cout << "No\n";
			continue;
		}
		if(x == w) {
			cout << "Yes\n";
			continue;
		}
		if(f - y == 1) {
			if(vip[{x,y}] == 1 || vip[{w,f}] == 1) cout << "Yes\n";
			else cout << "No\n";
			continue;
		}
		int pos1 = lower_bound(v.begin(),v.end(),x) - v.begin();
		int pos2 = lower_bound(v.begin(),v.end(),w-1) - v.begin();
		if(pos1 == sz(v) || pos2 == sz(v) || pos2 - pos1 + 1 != (w-1)-x + 1) {
			cout << "No\n";
			continue;
		}
		bool tr = 0;
		while(x != w) {
			if(!sz(vis[x])) {
				tr = 1;
				break;
			}
			int p = INT_MAX;
			for(auto j : vis[x]) {
				if(j >= y && p > j) p = j;
			}
			if(p > f) {
				tr = 1;
				break;
			}
			x++;
			y = p;
		}
		if(tr) cout << "No\n";
		else cout << "Yes\n";
	}
}

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