Submission #727641

#	Time	Username	Problem	Language	Result	Execution time	Memory
727641		SanguineChameleon	New Home (APIO18_new_home)	C++17	100 / 100	3763 ms	113628 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;
int tr[maxn * 4];
store S[maxn];
query Q[maxn];
set<int> bad[maxn];
set<int> val_pos[maxn];
int res[maxn];
int n, k, q;

void update(int id, int lt, int rt, int pos, int val) {
	if (lt == rt) {
		tr[id] = val;
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, val);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, val);
	}
	tr[id] = max(tr[id * 2], tr[id * 2 + 1]);
}

int get(int id, int lt, int rt, int pos) {
	if (lt == rt) {
		return tr[id];
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		return get(id * 2, lt, mt, pos);
	}
	else {
		return max(tr[id * 2], get(id * 2 + 1, mt + 1, rt, pos));
	}
}

void add_bad(int lt, int rt, int val) {
	if (lt > rt) {
		return;
	}
	if (rt == n) {
		rt += val - 1;
	}
	bad[lt].insert(rt);
	update(1, 1, n, lt, (bad[lt].empty() ? -inf : *bad[lt].rbegin()));
}

void rem_bad(int lt, int rt, int val) {
	if (lt > rt) {
		return;
	}
	if (rt == n) {
		rt += val - 1;
	}
	bad[lt].erase(rt);
	update(1, 1, n, lt, (bad[lt].empty() ? -inf : *bad[lt].rbegin()));
}

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;
	}
	return get(1, 1, n, lt) < rt;
}

void just_do_it() {
	fill_n(tr, maxn * 4, -inf);
	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: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20