답안 #934935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934935	2024-02-28T08:06:13 Z	IBory	새 집 (APIO18_new_home)	C++17	57 / 100	2871 ms	498348 KB

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> P[SZ], E[SZ];
	int T[SZ << 1];
	Seg() {
		fill(T, T + SZ * 2, -1E9);
	}
	void Update(int i, int v, bool e) {
		(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) {
		if (0 < id && id < SZ) {
			int pos = P[abs(id)], type = S[abs(id)];
			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);
			}
		}
		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) {
		if (id < SZ) {
			int pos = P[abs(id)], type = S[abs(id)];
			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);

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

			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--;
		}
		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

new_home.cpp: In member function 'void Seg::Update(int, int, bool)':
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());
      |     ~~^~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	205652 KB	Output is correct
2	Correct	45 ms	205660 KB	Output is correct
3	Correct	44 ms	205648 KB	Output is correct
4	Correct	44 ms	205652 KB	Output is correct
5	Correct	48 ms	205908 KB	Output is correct
6	Correct	46 ms	205900 KB	Output is correct
7	Correct	45 ms	205660 KB	Output is correct
8	Correct	45 ms	205912 KB	Output is correct
9	Correct	48 ms	205652 KB	Output is correct
10	Correct	46 ms	205992 KB	Output is correct
11	Correct	45 ms	205660 KB	Output is correct
12	Correct	46 ms	205768 KB	Output is correct
13	Correct	46 ms	205708 KB	Output is correct
14	Correct	46 ms	205648 KB	Output is correct
15	Correct	49 ms	205700 KB	Output is correct
16	Correct	45 ms	205908 KB	Output is correct
17	Correct	45 ms	205908 KB	Output is correct
18	Correct	44 ms	205712 KB	Output is correct
19	Correct	45 ms	205900 KB	Output is correct
20	Correct	46 ms	205768 KB	Output is correct
21	Correct	45 ms	205648 KB	Output is correct
22	Correct	46 ms	205652 KB	Output is correct
23	Correct	45 ms	205648 KB	Output is correct
24	Correct	45 ms	205908 KB	Output is correct
25	Correct	45 ms	205908 KB	Output is correct
26	Correct	45 ms	205916 KB	Output is correct
27	Correct	45 ms	205700 KB	Output is correct
28	Correct	45 ms	205688 KB	Output is correct
29	Correct	49 ms	205744 KB	Output is correct
30	Correct	46 ms	205648 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	205652 KB	Output is correct
2	Correct	45 ms	205660 KB	Output is correct
3	Correct	44 ms	205648 KB	Output is correct
4	Correct	44 ms	205652 KB	Output is correct
5	Correct	48 ms	205908 KB	Output is correct
6	Correct	46 ms	205900 KB	Output is correct
7	Correct	45 ms	205660 KB	Output is correct
8	Correct	45 ms	205912 KB	Output is correct
9	Correct	48 ms	205652 KB	Output is correct
10	Correct	46 ms	205992 KB	Output is correct
11	Correct	45 ms	205660 KB	Output is correct
12	Correct	46 ms	205768 KB	Output is correct
13	Correct	46 ms	205708 KB	Output is correct
14	Correct	46 ms	205648 KB	Output is correct
15	Correct	49 ms	205700 KB	Output is correct
16	Correct	45 ms	205908 KB	Output is correct
17	Correct	45 ms	205908 KB	Output is correct
18	Correct	44 ms	205712 KB	Output is correct
19	Correct	45 ms	205900 KB	Output is correct
20	Correct	46 ms	205768 KB	Output is correct
21	Correct	45 ms	205648 KB	Output is correct
22	Correct	46 ms	205652 KB	Output is correct
23	Correct	45 ms	205648 KB	Output is correct
24	Correct	45 ms	205908 KB	Output is correct
25	Correct	45 ms	205908 KB	Output is correct
26	Correct	45 ms	205916 KB	Output is correct
27	Correct	45 ms	205700 KB	Output is correct
28	Correct	45 ms	205688 KB	Output is correct
29	Correct	49 ms	205744 KB	Output is correct
30	Correct	46 ms	205648 KB	Output is correct
31	Correct	525 ms	238992 KB	Output is correct
32	Correct	214 ms	217044 KB	Output is correct
33	Correct	525 ms	238848 KB	Output is correct
34	Correct	550 ms	237512 KB	Output is correct
35	Correct	571 ms	239504 KB	Output is correct
36	Correct	578 ms	239792 KB	Output is correct
37	Correct	356 ms	238364 KB	Output is correct
38	Correct	362 ms	238540 KB	Output is correct
39	Correct	296 ms	237512 KB	Output is correct
40	Correct	308 ms	238272 KB	Output is correct
41	Correct	290 ms	228040 KB	Output is correct
42	Correct	269 ms	227780 KB	Output is correct
43	Correct	146 ms	219844 KB	Output is correct
44	Correct	273 ms	228040 KB	Output is correct
45	Correct	276 ms	227924 KB	Output is correct
46	Correct	285 ms	227268 KB	Output is correct
47	Correct	170 ms	224200 KB	Output is correct
48	Correct	196 ms	225136 KB	Output is correct
49	Correct	208 ms	226248 KB	Output is correct
50	Correct	204 ms	225728 KB	Output is correct
51	Correct	212 ms	226664 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1965 ms	277544 KB	Output is correct
2	Correct	2860 ms	320212 KB	Output is correct
3	Correct	715 ms	255160 KB	Output is correct
4	Correct	1649 ms	281464 KB	Output is correct
5	Correct	2684 ms	320284 KB	Output is correct
6	Correct	2871 ms	320520 KB	Output is correct
7	Correct	649 ms	255168 KB	Output is correct
8	Correct	1290 ms	275360 KB	Output is correct
9	Correct	1871 ms	298596 KB	Output is correct
10	Correct	2184 ms	320032 KB	Output is correct
11	Correct	1452 ms	315992 KB	Output is correct
12	Correct	1566 ms	316120 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	818 ms	498348 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	205652 KB	Output is correct
2	Correct	45 ms	205660 KB	Output is correct
3	Correct	44 ms	205648 KB	Output is correct
4	Correct	44 ms	205652 KB	Output is correct
5	Correct	48 ms	205908 KB	Output is correct
6	Correct	46 ms	205900 KB	Output is correct
7	Correct	45 ms	205660 KB	Output is correct
8	Correct	45 ms	205912 KB	Output is correct
9	Correct	48 ms	205652 KB	Output is correct
10	Correct	46 ms	205992 KB	Output is correct
11	Correct	45 ms	205660 KB	Output is correct
12	Correct	46 ms	205768 KB	Output is correct
13	Correct	46 ms	205708 KB	Output is correct
14	Correct	46 ms	205648 KB	Output is correct
15	Correct	49 ms	205700 KB	Output is correct
16	Correct	45 ms	205908 KB	Output is correct
17	Correct	45 ms	205908 KB	Output is correct
18	Correct	44 ms	205712 KB	Output is correct
19	Correct	45 ms	205900 KB	Output is correct
20	Correct	46 ms	205768 KB	Output is correct
21	Correct	45 ms	205648 KB	Output is correct
22	Correct	46 ms	205652 KB	Output is correct
23	Correct	45 ms	205648 KB	Output is correct
24	Correct	45 ms	205908 KB	Output is correct
25	Correct	45 ms	205908 KB	Output is correct
26	Correct	45 ms	205916 KB	Output is correct
27	Correct	45 ms	205700 KB	Output is correct
28	Correct	45 ms	205688 KB	Output is correct
29	Correct	49 ms	205744 KB	Output is correct
30	Correct	46 ms	205648 KB	Output is correct
31	Correct	525 ms	238992 KB	Output is correct
32	Correct	214 ms	217044 KB	Output is correct
33	Correct	525 ms	238848 KB	Output is correct
34	Correct	550 ms	237512 KB	Output is correct
35	Correct	571 ms	239504 KB	Output is correct
36	Correct	578 ms	239792 KB	Output is correct
37	Correct	356 ms	238364 KB	Output is correct
38	Correct	362 ms	238540 KB	Output is correct
39	Correct	296 ms	237512 KB	Output is correct
40	Correct	308 ms	238272 KB	Output is correct
41	Correct	290 ms	228040 KB	Output is correct
42	Correct	269 ms	227780 KB	Output is correct
43	Correct	146 ms	219844 KB	Output is correct
44	Correct	273 ms	228040 KB	Output is correct
45	Correct	276 ms	227924 KB	Output is correct
46	Correct	285 ms	227268 KB	Output is correct
47	Correct	170 ms	224200 KB	Output is correct
48	Correct	196 ms	225136 KB	Output is correct
49	Correct	208 ms	226248 KB	Output is correct
50	Correct	204 ms	225728 KB	Output is correct
51	Correct	212 ms	226664 KB	Output is correct
52	Correct	150 ms	221056 KB	Output is correct
53	Correct	146 ms	219060 KB	Output is correct
54	Correct	269 ms	226760 KB	Output is correct
55	Correct	267 ms	225848 KB	Output is correct
56	Correct	223 ms	224760 KB	Output is correct
57	Correct	281 ms	227408 KB	Output is correct
58	Correct	234 ms	224872 KB	Output is correct
59	Correct	211 ms	223728 KB	Output is correct
60	Correct	264 ms	227012 KB	Output is correct
61	Correct	119 ms	219844 KB	Output is correct
62	Correct	165 ms	221128 KB	Output is correct
63	Correct	237 ms	224160 KB	Output is correct
64	Correct	245 ms	225224 KB	Output is correct
65	Correct	292 ms	227016 KB	Output is correct
66	Correct	285 ms	228148 KB	Output is correct
67	Correct	187 ms	218300 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	205652 KB	Output is correct
2	Correct	45 ms	205660 KB	Output is correct
3	Correct	44 ms	205648 KB	Output is correct
4	Correct	44 ms	205652 KB	Output is correct
5	Correct	48 ms	205908 KB	Output is correct
6	Correct	46 ms	205900 KB	Output is correct
7	Correct	45 ms	205660 KB	Output is correct
8	Correct	45 ms	205912 KB	Output is correct
9	Correct	48 ms	205652 KB	Output is correct
10	Correct	46 ms	205992 KB	Output is correct
11	Correct	45 ms	205660 KB	Output is correct
12	Correct	46 ms	205768 KB	Output is correct
13	Correct	46 ms	205708 KB	Output is correct
14	Correct	46 ms	205648 KB	Output is correct
15	Correct	49 ms	205700 KB	Output is correct
16	Correct	45 ms	205908 KB	Output is correct
17	Correct	45 ms	205908 KB	Output is correct
18	Correct	44 ms	205712 KB	Output is correct
19	Correct	45 ms	205900 KB	Output is correct
20	Correct	46 ms	205768 KB	Output is correct
21	Correct	45 ms	205648 KB	Output is correct
22	Correct	46 ms	205652 KB	Output is correct
23	Correct	45 ms	205648 KB	Output is correct
24	Correct	45 ms	205908 KB	Output is correct
25	Correct	45 ms	205908 KB	Output is correct
26	Correct	45 ms	205916 KB	Output is correct
27	Correct	45 ms	205700 KB	Output is correct
28	Correct	45 ms	205688 KB	Output is correct
29	Correct	49 ms	205744 KB	Output is correct
30	Correct	46 ms	205648 KB	Output is correct
31	Correct	525 ms	238992 KB	Output is correct
32	Correct	214 ms	217044 KB	Output is correct
33	Correct	525 ms	238848 KB	Output is correct
34	Correct	550 ms	237512 KB	Output is correct
35	Correct	571 ms	239504 KB	Output is correct
36	Correct	578 ms	239792 KB	Output is correct
37	Correct	356 ms	238364 KB	Output is correct
38	Correct	362 ms	238540 KB	Output is correct
39	Correct	296 ms	237512 KB	Output is correct
40	Correct	308 ms	238272 KB	Output is correct
41	Correct	290 ms	228040 KB	Output is correct
42	Correct	269 ms	227780 KB	Output is correct
43	Correct	146 ms	219844 KB	Output is correct
44	Correct	273 ms	228040 KB	Output is correct
45	Correct	276 ms	227924 KB	Output is correct
46	Correct	285 ms	227268 KB	Output is correct
47	Correct	170 ms	224200 KB	Output is correct
48	Correct	196 ms	225136 KB	Output is correct
49	Correct	208 ms	226248 KB	Output is correct
50	Correct	204 ms	225728 KB	Output is correct
51	Correct	212 ms	226664 KB	Output is correct
52	Correct	1965 ms	277544 KB	Output is correct
53	Correct	2860 ms	320212 KB	Output is correct
54	Correct	715 ms	255160 KB	Output is correct
55	Correct	1649 ms	281464 KB	Output is correct
56	Correct	2684 ms	320284 KB	Output is correct
57	Correct	2871 ms	320520 KB	Output is correct
58	Correct	649 ms	255168 KB	Output is correct
59	Correct	1290 ms	275360 KB	Output is correct
60	Correct	1871 ms	298596 KB	Output is correct
61	Correct	2184 ms	320032 KB	Output is correct
62	Correct	1452 ms	315992 KB	Output is correct
63	Correct	1566 ms	316120 KB	Output is correct
64	Runtime error	818 ms	498348 KB	Execution killed with signal 11
65	Halted	0 ms	0 KB	-

답안 #934935

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0