Submission #1144928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144928		Agageldi	Trampoline (info1cup20_trampoline)	C++20	42 / 100	2099 ms	70756 KiB

trampoline

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

#define ll long long
#define N 600005
#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>

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

void solve(int x,int y,int z,int k){
	b[1] = vis[x];
	b[2] = vis[y];
	b[3] = vis[z];
	b[4] = vis[k];
}

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;
		vis[x] = vis[y] = 1;
		p.pb({x,y});
	}
	cin >> T;
	for(int i = 1; i <= T; i++) {
		int x, y, w, f;
		cin >> x >> y >> w >> f;
		t1.pb({x,y});
		t2.pb({w,f});
		vis[x] = vis[y] = vis[w] = vis[f] = 1;
	}
	for(auto i:vis) {
		vis[i.ff] = ++inx;
	}
	for(auto i:p) {
		i.ff = vis[i.ff];
		i.ss = vis[i.ss];
		v[i.ff].insert(i.ss);
	}
	for(int i = 0;i<sz(t1);i++) {
		solve(t1[i].ff,t1[i].ss,t2[i].ff,t2[i].ss);
		if(b[1] > b[3] || b[2] > b[4]) {
			cout << "No\n";
			continue;
		}
		if(b[1] == b[3]) {
			cout << "Yes\n";
			continue;
		}
		bool tr = 0;
		while(b[1] != b[3]) {
			if(!sz(v[b[1]]) || *(--v[b[1]].end()) < b[2]) {
				tr = 1;
				break;
			}
			int p = *lower_bound(v[b[1]].begin(),v[b[1]].end(),b[2]);
			if(p > b[4]) {
				tr = 1;
				break;
			}
			b[1]++;
			b[2] = p;
		}
		if(tr == 1) cout << "No\n";
		else cout << "Yes\n";
	}
}

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