Submission #934798

#	Time	Username	Problem	Language	Result	Execution time	Memory
934798		IBory	New Home (APIO18_new_home)	C++17	0 / 100	5075 ms	896384 KiB

new_home

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 300003, LIM = 10000000, SZ = 1 << 27;
int P[MAX], S[MAX], X[MAX], ans[MAX];
multiset<int> CX[MAX];

struct Seg {
	priority_queue<int> T[LIM], E[LIM];
	int CL[LIM], CR[LIM], CN;
	void Clear() {
		for (int i = 0; i < LIM; ++i) {
			while (!T[i].empty()) T[i].pop();
			while (!E[i].empty()) E[i].pop();
		}
		memset(CL, -1, sizeof(CL));
		memset(CR, -1, sizeof(CR));
		CN = 1;
	}
	void Update(int L, int R, int v, bool e, int sL = 1, int sR = SZ, int n = 1) {
		if (n == 1) {
			if (v < 0 && R != SZ) R = L + (R - L) / 2;
			else if (v > 0 && L != 1) L = R - (R - L) / 2;
		}

		if (R < sL || sR < L) return;
		if (L <= sL && sR <= R) {
			(e ? E[n] : T[n]).push(v);
			return;
		}
		int mid = (sL + sR) >> 1;
		if (CL[n] == -1) CL[n] = ++CN;
		if (CR[n] == -1) CR[n] = ++CN;
		Update(L, R, v, e, sL, mid, CL[n]);
		Update(L, R, v, e, mid + 1, sR, CR[n]);
	}
	int Query(int p) {
		int sL = 1, sR = SZ, n = 1, ret = -1e9;
		while (1) {
			if (n == -1) break;
			while (!T[n].empty() && !E[n].empty() && T[n].top() == E[n].top()) T[n].pop(), E[n].pop();
			if (!T[n].empty()) ret = max(ret, T[n].top());

			if (sL == sR) break;
			int mid = (sL + sR) >> 1;
			if (p <= mid) sR = mid, n = CL[n];
			else sL = mid + 1, n = CR[n];
		}
		// cout << p << ' ' << ret << '\n';
		return ret;
	}
} T;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<pii> ord;
	for (int i = 1; i <= N; ++i) {
		int a, b;
		cin >> P[i] >> S[i] >> a >> b;
		ord.emplace_back(a, i);
		ord.emplace_back(b + 1, -i);
	}
	for (int i = 1; i <= Q; ++i) {
		int t;
		cin >> X[i] >> t;
		ord.emplace_back(t, MAX + i);
	}
	
	// Process 1: a = 1
	int curOpen = 0;
	memset(ans, 0xf3, sizeof(ans));
	sort(ord.begin(), ord.end());
	for (auto [_, id] : ord) {
		// Insert / Modify Line
		if (0 < id && id < MAX) {
			// cout << "Insert " << id << '\n';
			
			int cur = P[id], type = S[id];
			if (CX[type].empty()) curOpen++;
			auto it = CX[type].insert(cur);
			int L = (it == CX[type].begin() ? -1 : *prev(it));
			int R = (next(it) == CX[type].end() ? SZ : *next(it) - 1);

			if (L != -1) {
				T.Update(L, R, -L, 1);
				T.Update(L, cur - 1, -L, 0);
			}
			T.Update(cur, R, -cur, 0);
		}
		// Erase / Modify Line
		else if (id < 0) {
			// cout << "Erase " << -id << '\n';

			id = abs(id);
			int cur = P[id], type = S[id];
			auto it = CX[type].find(cur);
			int L = (it == CX[type].begin() ? -1 : *prev(it));
			int R = (next(it) == CX[type].end() ? SZ : *next(it) - 1);

			if (L != -1) {
				T.Update(L, R, -L, 0);
				T.Update(L, cur - 1, -L, 1);
			}
			T.Update(cur, R, -cur, 1);

			CX[type].erase(it);
			if (CX[type].empty()) curOpen--;
		}
		// Query
		else {
			id -= MAX;
			// cout << "Query " << id << '\n';
			if (curOpen == K) ans[id] = max(ans[id], X[id] + T.Query(X[id]));
		}
	}

	// cout << "-------------\n";

	// Process 2: a = -1
	T.Clear();
	for (auto [_, id] : ord) {
		// Insert / Modify Line
		if (0 < id && id < MAX) {
			
			int cur = P[id], type = S[id];
			if (CX[type].empty()) curOpen++;
			auto it = CX[type].insert(cur);
			int L = (it == CX[type].begin() ? 1 : *prev(it) + 1);
			int R = (next(it) == CX[type].end() ? -1 : *next(it));

			if (R != -1) {
				T.Update(L, R, R, 1);
				T.Update(cur + 1, R, R, 0);
			}
			T.Update(L, cur, cur, 0);
		}
		// Erase / Modify Line
		else if (id < 0) {
			id = abs(id);
			int cur = P[id], type = S[id];
			auto it = CX[type].find(cur);
			int L = (it == CX[type].begin() ? 1 : *prev(it) + 1);
			int R = (next(it) == CX[type].end() ? -1 : *next(it));

			if (R != -1) {
				T.Update(L, R, R, 0);
				T.Update(cur + 1, R, R, 1);
			}
			T.Update(L, cur, cur, 1);

			CX[type].erase(it);
			if (CX[type].empty()) curOpen--;
		}
		// Query
		else {
			id -= MAX;
			// cout << "Query " << id << '\n';
			if (curOpen == K) ans[id] = max(ans[id], -X[id] + T.Query(X[id]));
		}
	}

	for (int i = 1; i <= Q; ++i) cout << (ans[i] < 0 ? -1 : ans[i]) << '\n';
	return 0;
}

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