Submission #727640

#	Time	Username	Problem	Language	Result	Execution time	Memory
727640		SanguineChameleon	New Home (APIO18_new_home)	C++17	5 / 100	5062 ms	88048 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];
set<int> bad[maxn];
set<int> val_pos[maxn];
int res[maxn];
int n, k, q;

void add_bad(int lt, int rt, int val) {
	if (lt > rt) {
		return;
	}
	if (rt == n) {
		rt += val - 1;
	}
	bad[lt].insert(rt);
}

void rem_bad(int lt, int rt, int val) {
	if (lt > rt) {
		return;
	}
	if (rt == n) {
		rt += val - 1;
	}
	bad[lt].erase(rt);
}

void add_val(int pos, int val) {
	auto it = val_pos[val].insert(pos).first;
	int prv = (it == val_pos[val].begin() ? 0 : *prev(it));
	int nxt = (next(it) == val_pos[val].end() ? n + 1 : *next(it));
	rem_bad(prv + 1, nxt - 1, val);
	add_bad(prv + 1, pos - 1, val);
	add_bad(pos + 1, nxt - 1, val);
}

void rem_val(int pos, int val) {
	auto it = val_pos[val].lower_bound(pos);
	int prv = (it == val_pos[val].begin() ? 0 : *prev(it));
	int nxt = (next(it) == val_pos[val].end() ? n + 1 : *next(it));
	rem_bad(prv + 1, pos - 1, val);
	rem_bad(pos + 1, nxt - 1, val);
	add_bad(prv + 1, nxt - 1, val);
	val_pos[val].erase(it);
}

bool check(int lt, int rt) {
	if (lt > rt) {
		return false;
	}
	for (int i = 1; i <= lt; i++) {
		if (!bad[i].empty() && *bad[i].rbegin() >= rt) {
			return false;
		}
	}
	return true;
}

void just_do_it() {
	cin >> n >> k >> q;
	for (int i = 1; i <= k; i++) {
		add_bad(1, n, i);
	}
	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_val(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 (check(ql, qr)) {
					res[id] = mt;
					rt = mt - 1;
				}
				else {
					lt = mt + 1;
				}
			}
		}
		if (type == 3) {
			rem_val(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