Submission #934924

#	Time	Username	Problem	Language	Result	Execution time	Memory
934924		IBory	New Home (APIO18_new_home)	C++17	100 / 100	4024 ms	550496 KiB

new_home

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

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

struct Seg {
	priority_queue<int> P[SZ], E[SZ];
	int T[SZ << 1];
	Seg() {
		fill(T, T + SZ * 2, -1E9);
	}
	void Update(int i, int v, bool e, int sL = 1, int sR = SZ, int n = 1) {
		(e ? E[i] : P[i]).push(v);
		while (!E[i].empty() && !P[i].empty() && E[i].top() == P[i].top()) E[i].pop(), P[i].pop();
		T[i += SZ - 1] = (P[i].empty() ? -1e9 : P[i].top());
		while (i >>= 1) T[i] = max(T[i * 2], T[i * 2 + 1]);
	}
	int Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		if (R < sL || sR < L) return -1e9;
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return max(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, 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, pos, out);
			T1.Update(nh, -pos, out);

			// Modify
			if (isNext) {
				T2.Update(isPrev ? all : L_LIM, *next(it), !out);
				T2.Update(nh, *next(it), out);
			}
			if (isPrev) {
				T1.Update(isNext ? all : R_LIM, -*prev(it), !out);
				T1.Update(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, SZ);
			int b2 = T2.Query(1, 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, bool, int, int, int)':
new_home.cpp:18:7: warning: operation on 'i' may be undefined [-Wsequence-point]
   18 |   T[i += SZ - 1] = (P[i].empty() ? -1e9 : P[i].top());
      |     ~~^~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:90:45: warning: unused variable 'x' [-Wunused-variable]
   90 |    int pos = P[abs(id)], type = S[abs(id)], x = Find(pos);
      |                                             ^

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