Submission #1172685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172685		stdfloat	New Home (APIO18_new_home)	C++20	12 / 100	5094 ms	86144 KiB

new_home

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, K, q;
	cin >> n >> K >> q;

	map<int, vector<pii>> m;
	for (int i = 1; i <= n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;

		m[a].push_back({x, t});
		m[b + 1].push_back({-x, t});
	}

	for (int i = 1; i <= q; i++) {
		int l, y;
		cin >> l >> y;

		m[y].push_back({l, -i});
	}

	vector<int> ans(q + 1);
	vector<multiset<int>> s(K + 1);
	for (auto i : m) {
		for (auto [x, t] : i.ss) {
			if (x < 0) s[t].erase(s[t].find(-x));
			else if (0 < t) s[t].insert(x);
		}

		for (auto [x, t] : i.ss) {
			if (0 < t) continue;
		
			t = -t;
			for (int j = 1; j <= K; j++) {
				if (s[j].empty()) {
					ans[t] = -1;
					break;
				}

				auto z = s[j].upper_bound(x);

				int mn = INT_MAX;
				if (z != s[j].end()) mn = *z - x;
				if (z != s[j].begin()) mn = min(mn, x - *--z); 
			
				ans[t] = max(ans[t], mn);
			}
		}
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

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