Submission #1201684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201684		crispxx	New Home (APIO18_new_home)	C++20	5 / 100	5121 ms	805268 KiB

new_home

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

int g[100000000];

void solve() {
	int n, k, q; cin >> n >> k >> q;
	
	vector<int> x(n), t(n), a(n), b(n);
	
	vector<vector<ar<int, 3>>> type(k);
	
	for(int i = 0; i < 100000000; i++) g[i] = LLONG_MAX;
	
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> t[i] >> a[i] >> b[i];
		t[i]--;
		type[t[i]].pb({x[i], a[i], b[i]});
	}
	
	auto query = [&](int l, int y) -> int {
		int ans = 0;
		for(int i = 0; i < k; i++) {
			int mn = 1e9;
			for(auto [X, A, B] : type[i]) {
				if(y >= A && y <= B) {
					mn = min(mn, abs(X - l));
				}
			}
			if(mn == 1e9) return -1;
			ans = max(ans, mn);
		}
		return ans;
	};
	
	while(q--) {
		int l, y; cin >> l >> y;
		cout << query(l, y) << nl;
	}
}

/**
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1


**/

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20