Submission #934904

#	Time	Username	Problem	Language	Result	Execution time	Memory
934904		IBory	New Home (APIO18_new_home)	C++17	47 / 100	5096 ms	535808 KiB

new_home

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

const int SZ = 1 << 20;
int P[SZ], S[SZ], X[SZ], ans[SZ];
multiset<int> CX[SZ];

struct Seg {
	priority_queue<int> T[SZ << 1], E[SZ << 1];
	int CL[SZ << 1], CR[SZ << 1];

	void Update(int L, int R, int v, bool e) {
		int sL = 1, sR = SZ, n = 1;
		queue<tuple<int, int, int>> Q;
		Q.emplace(1, SZ, 1);
		while (!Q.empty()) {
			auto [sL, sR, n] = Q.front(); Q.pop();
			if (R < sL || sR < L) continue;
			if (L <= sL && sR <= R) {
				(e ? E[n] : T[n]).push(v);
				continue;
			}
			int mid = (sL + sR) >> 1;
			Q.emplace(sL, mid, n * 2);
			Q.emplace(mid + 1, sR, n * 2 + 1);
		}
	}
	int Query(int p) {
		int sL = 1, sR = SZ, n = 1, ret = -1e9;
		while (1) {
			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) return ret;
			int mid = (sL + sR) >> 1;
			if (p <= mid) sR = mid, n = n * 2;
			else sL = mid + 1, n = n * 2 + 1;
		}
	}
} T1, T2;

vector<int> UX;
int Find(int x) {
	return lower_bound(UX.begin(), UX.end(), x) - UX.begin();
}

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;
		P[i] <<= 1;
		ord.emplace_back(a, i);
		ord.emplace_back(b + 1, -i);
	}
	for (int i = 1; i <= Q; ++i) {
		int t;
		cin >> X[i] >> t;
		X[i] <<= 1;
		ord.emplace_back(t, SZ + i);
	}
	sort(ord.begin(), ord.end());

	UX.push_back(-1); UX.push_back(1); UX.push_back(1e8);
	for (auto [_, id] : ord) {
		// Line Add
		if (0 < id && id < SZ) {
			int pos = P[abs(id)], type = S[abs(id)];
			UX.push_back(pos);
			auto it = CX[type].insert(pos);
			if (it != CX[type].begin()) {
				int h = abs(pos - *prev(it)) / 2;
				UX.push_back(*prev(it) + h);
			}
			if (next(it) != CX[type].end()) {
				int h = abs(pos - *next(it)) / 2;
				UX.push_back(pos + h);
			}
		}
		// Line Erase
		else if (id < 0) {
			int pos = P[abs(id)], type = S[abs(id)];
			auto it = CX[type].find(pos);
			if (it != CX[type].begin() && next(it) != CX[type].end()) {
				int h = abs(*next(it) - *prev(it)) / 2;
				UX.push_back(*prev(it) + h);
			}
			CX[type].erase(it);
		}
		else UX.push_back(X[id - SZ]);
	}
	sort(UX.begin(), UX.end());
	UX.erase(unique(UX.begin(), UX.end()), UX.end());

	memset(ans, 0xf3, sizeof(ans));
	int curOpen = 0, L_LIM = 1, R_LIM = UX.size() - 1;
	for (auto [_, id] : ord) {
		// Line Add/Erase
		if (id < SZ) {
			int pos = P[abs(id)], type = S[abs(id)], x = Find(pos);
			bool out = id < 0;

			if (CX[type].empty()) curOpen++;
			auto it = (out ? CX[type].find(pos) : CX[type].insert(pos));
			bool isPrev = it != CX[type].begin();
			bool isNext = next(it) != CX[type].end();
			int ph = (isPrev ? Find(pos - (pos - *prev(it)) / 2) : L_LIM);
			int nh = (isNext ? Find(pos + (*next(it) - pos) / 2) : R_LIM);
			int all = (isPrev && isNext ? Find(*next(it) - (*next(it) - *prev(it)) / 2) : 0);

			// Add
			T2.Update(ph, x, pos, out);
			T1.Update(x, nh, -pos, out);

			// Modify
			if (isNext) {
				int nx = Find(*next(it));
				T2.Update(isPrev ? all : L_LIM, nx, *next(it), !out);
				T2.Update(nh, nx, *next(it), out);
			}
			if (isPrev) {
				int px = Find(*prev(it));
				T1.Update(px, isNext ? all : R_LIM, -*prev(it), !out);
				T1.Update(px, ph, -*prev(it), out);
			}

			if (out) CX[type].erase(it);
			if (CX[type].empty()) curOpen--;
		}
		// Query
		else if (curOpen == K) {
			id -= SZ;
			int x = X[id], p = Find(x);
			int b1 = T1.Query(p);
			int b2 = T2.Query(p);
			ans[id] = max(x + b1, b2 - x);
		}
	}

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

Compilation message (stderr)

new_home.cpp: In member function 'void Seg::Update(int, int, int, bool)':
new_home.cpp:14:7: warning: unused variable 'sL' [-Wunused-variable]
   14 |   int sL = 1, sR = SZ, n = 1;
      |       ^~
new_home.cpp:14:15: warning: unused variable 'sR' [-Wunused-variable]
   14 |   int sL = 1, sR = SZ, n = 1;
      |               ^~
new_home.cpp:14:24: warning: unused variable 'n' [-Wunused-variable]
   14 |   int sL = 1, sR = SZ, n = 1;
      |                        ^

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