Submission #727638

#	Time	Username	Problem	Language	Result	Execution time	Memory
727638		SanguineChameleon	New Home (APIO18_new_home)	C++17	5 / 100	5047 ms	38044 KiB

new_home

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct store {
	int pos, type, left_T, right_T;
};

struct query {
	int pos, T;
};

const int inf = 1e8 + 20;
const int maxn = 3e5 + 20;
store S[maxn];
query Q[maxn];
int res[maxn];
int A[maxn];
int n, k, q;

void add(int pos, int val) {
	A[pos] = val;
}

void rem(int pos, int val) {
	A[pos] = 0;
}

bool check(int lt, int rt) {
	set<int> types;
	for (int i = lt; i <= rt; i++) {
		if (A[i]) {
			types.insert(A[i]);
		}
	}
	return (int)types.size() == k;
}

void just_do_it() {
	cin >> n >> k >> q;
	vector<pair<int, int>> sorted_pos;
	vector<pair<int, pair<int, int>>> events;
	for (int i = 1; i <= n; i++) {
		cin >> S[i].pos >> S[i].type >> S[i].left_T >> S[i].right_T;
		sorted_pos.push_back({S[i].pos, i});
		events.push_back({S[i].left_T, {1, i}});
		events.push_back({S[i].right_T, {3, i}});
	}
	sort(sorted_pos.begin(), sorted_pos.end());
	for (int i = 1; i <= n; i++) {
		S[sorted_pos[i - 1].second].pos = i;
	}
	for (int i = 1; i <= q; i++) {
		cin >> Q[i].pos >> Q[i].T;
		events.push_back({Q[i].T, {2, i}});
	}
	sort(events.begin(), events.end());
	for (auto e: events) {
		int type = e.second.first;
		int id = e.second.second;
		if (type == 1) {
			add(S[id].pos, S[id].type);
		}
		if (type == 2) {
			res[id] = -1;
			int lt = 0;
			int rt = inf;
			while (lt <= rt) {
				int mt = (lt + rt) / 2;
				int ql = lower_bound(sorted_pos.begin(), sorted_pos.end(), make_pair(Q[id].pos - mt, -inf)) - sorted_pos.begin() + 1;
				int qr = upper_bound(sorted_pos.begin(), sorted_pos.end(), make_pair(Q[id].pos + mt, inf)) - sorted_pos.begin();
				if (ql <= qr && check(ql, qr)) {
					res[id] = mt;
					rt = mt - 1;
				}
				else {
					lt = mt + 1;
				}
			}
		}
		if (type == 3) {
			rem(S[id].pos, S[id].type);
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << res[i] << '\n';
	}
}

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