oj.uz

Submission #950864

# Submission time Handle Problem Language Result Execution time Memory
950864 2024-03-20T20:41:29 Z MinaRagy06 New Home (APIO18_new_home) C++17
47 / 100
 5000 ms 242968 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r) >> 1)

const int N = 300'005;
// set<array<int, 3>> gud[N];
struct segtree {
	set<array<int, 3>> seg[1 << 20];
	void insert(int i, int l, int r, int s, int e, array<int, 3> v) {
		if (s <= l && r <= e) {
			seg[i].insert(v);
			return;
		}
		if (r < s || e < l) {
			return;
		}
		insert(i << 1, l, mid, s, e, v);
		insert(i << 1 | 1, mid + 1, r, s, e, v);
		if (seg[i << 1].find(v) != seg[i << 1].end() && seg[i << 1 | 1].find(v) != seg[i << 1 | 1].end()) {
			seg[i].insert(v);
			seg[i << 1].erase(v);
			seg[i << 1 | 1].erase(v);
		}
	}
	void erase(int i, int l, int r, int s, int e, array<int, 3> v) {
		if (s <= l && r <= e) {
			seg[i].erase(v);
			return;
		}
		if (r < s || e < l) {
			return;
		}
		if (seg[i].find(v) != seg[i].end()) {
			seg[i].erase(v);
			seg[i << 1].insert(v);
			seg[i << 1 | 1].insert(v);
		}
		erase(i << 1, l, mid, s, e, v);
		erase(i << 1 | 1, mid + 1, r, s, e, v);
	}
	void get(int i, int l, int r, int x, int xv, int &mx, int &cnt) {
		if (seg[i].size()) {
			mx = max(mx, abs(xv - (*seg[i].rbegin())[0]));
			mx = max(mx, abs(xv - (*seg[i].begin())[0]));
			cnt += seg[i].size();
		}
		if (l == r) {
			return;
		}
		if (x <= mid) {
			get(i << 1, l, mid, x, xv, mx, cnt);
		} else {
			get(i << 1 | 1, mid + 1, r, x, xv, mx, cnt);
		}
	}
} seg;
multiset<array<int, 2>> pos[N];
vector<array<int, 2>> ask[N];
vector<array<int, 3>> in[N], out[N];
int ans[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, k, q;
	cin >> n >> k >> q;
	array<int, 4> a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	}
	array<int, 2> qq[q];
	vector<int> v1, v2;
	for (int i = 0; i < q; i++) {
		cin >> qq[i][0] >> qq[i][1];
		v1.push_back(qq[i][0]);
		v2.push_back(qq[i][1]);
	}
	
	sort(v1.begin(), v1.end());
	v1.resize(unique(v1.begin(), v1.end()) - v1.begin());

	sort(v2.begin(), v2.end());
	v2.resize(unique(v2.begin(), v2.end()) - v2.begin());

	auto get = [&] (int s, int e, vector<int> &vv) {
		int l = lower_bound(vv.begin(), vv.end(), s) - vv.begin();
		int r = upper_bound(vv.begin(), vv.end(), e) - vv.begin() - 1;
		return (array<int, 2>) {l, r};
	};
	auto get2 = [&] (int x, vector<int> &vv) {
		return lower_bound(vv.begin(), vv.end(), x) - vv.begin();
	};
	
	for (int i = 0; i < n; i++) {
		array<int, 2> v = get(a[i][2], a[i][3], v2);
		if (v[0] > v[1]) continue;
		in[v[0]].push_back({a[i][0], a[i][1], i});
		out[v[1]].push_back({a[i][0], a[i][1], i});
	}
	for (int i = 0; i < q; i++) {
		ask[get2(qq[i][1], v2)].push_back({qq[i][0], i});
	}
	auto insert = [&] (int s, int e, int val, int t, int idx) {
		array<int, 2> v = get(s, e, v1);
		if (v[0] > v[1]) return void();
// 		cout << "+ " << v[0] << ' ' << v[1] << ' ' << idx << '\n';
		seg.insert(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// 		for (int i = v[0]; i <= v[1]; i++) {
// 			gud[i].insert({val, t, idx});
// 		}
	};
	auto erase = [&] (int s, int e, int val, int t, int idx) {
		array<int, 2> v = get(s, e, v1);
		if (v[0] > v[1]) return void();
// 		cout << "- " << v[0] << ' ' << v[1] << ' ' << idx << '\n';
		seg.erase(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// 		for (int i = v[0]; i <= v[1]; i++) {
// 			gud[i].erase({val, t, idx});
// 		}
	};
	for (int i = 0; i < v2.size(); i++) {
		for (auto [x, t, idx] : in[i]) {
			pos[t].insert({x, idx});
			auto it = pos[t].lower_bound({x, idx});
			int l = 0, r = 1e8;
			if (it != pos[t].begin()) {
				it--;
				array<int, 2> L = (*it);
				int md = (L[0] + x) / 2;
				it++;
				it++;
				int en = 1e8;
				if (it != pos[t].end()) {
					en = (L[0] + (*it)[0]) / 2;
				}
				it--;
				erase(md + 1, en, L[0], t, L[1]);
				l = md + 1;
			}
			if ((++it) != pos[t].end()) {
				array<int, 2> R = (*it);
				int md = (x + R[0]) / 2;
				it--;
				int st = 0;
				if (it != pos[t].begin()) {
					it--;
					st = ((*it)[0] + R[0]) / 2 + 1;
					it++;
				}
				it++;
				erase(st, md, R[0], t, R[1]);
				r = md;
			}
			it--;
			insert(l, r, x, t, idx);
		}

		for (auto [x, idx] : ask[i]) {
			int p = get2(x, v1);
			int mx = 0, cnt = 0;
			seg.get(1, 0, v1.size() - 1, p, x, mx, cnt);
// 			cout << "? " << p << ": " << cnt << '\n';
			if (cnt != k) {
				ans[idx] = -1;
				continue;
			}
			ans[idx] = mx;
		}
		
		for (auto [x, t, idx] : out[i]) {
			auto it = pos[t].lower_bound({x, idx});
			int l = 0, r = 1e8;
			if (it != pos[t].begin()) {
				it--;
				array<int, 2> L = (*it);
				int md = (L[0] + x) / 2;
				it++;
				it++;
				int en = 1e8;
				if (it != pos[t].end()) {
					en = (L[0] + (*it)[0]) / 2;
				}
				it--;
				insert(md + 1, en, L[0], t, L[1]);
				l = md + 1;
			}
			if ((++it) != pos[t].end()) {
				array<int, 2> R = (*it);
				int md = (x + R[0]) / 2;
				it--;
				int st = 0;
				if (it != pos[t].begin()) {
					it--;
					st = ((*it)[0] + R[0]) / 2 + 1;
					it++;
				}
				it++;
				insert(st, md, R[0], t, R[1]);
				r = md;
			}
			it--;
			erase(l, r, x, t, idx);
			pos[t].erase({x, idx});
		}
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 85844 KB Output is correct
2 Correct 19 ms 85856 KB Output is correct
3 Correct 18 ms 85848 KB Output is correct
4 Correct 18 ms 85852 KB Output is correct
5 Correct 20 ms 85980 KB Output is correct
6 Correct 20 ms 85852 KB Output is correct
7 Correct 19 ms 85852 KB Output is correct
8 Correct 21 ms 85868 KB Output is correct
9 Correct 19 ms 85848 KB Output is correct
10 Correct 21 ms 85852 KB Output is correct
11 Correct 20 ms 85852 KB Output is correct
12 Correct 20 ms 85868 KB Output is correct
13 Correct 21 ms 85852 KB Output is correct
14 Correct 21 ms 85848 KB Output is correct
15 Correct 20 ms 85852 KB Output is correct
16 Correct 19 ms 85840 KB Output is correct
17 Correct 20 ms 86012 KB Output is correct
18 Correct 20 ms 85848 KB Output is correct
19 Correct 23 ms 85848 KB Output is correct
20 Correct 20 ms 85852 KB Output is correct
21 Correct 18 ms 85852 KB Output is correct
22 Correct 19 ms 85852 KB Output is correct
23 Correct 21 ms 85852 KB Output is correct
24 Correct 21 ms 85852 KB Output is correct
25 Correct 21 ms 85852 KB Output is correct
26 Correct 21 ms 85852 KB Output is correct
27 Correct 20 ms 85852 KB Output is correct
28 Correct 20 ms 85848 KB Output is correct
29 Correct 20 ms 85940 KB Output is correct
30 Correct 19 ms 85852 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 85844 KB Output is correct
2 Correct 19 ms 85856 KB Output is correct
3 Correct 18 ms 85848 KB Output is correct
4 Correct 18 ms 85852 KB Output is correct
5 Correct 20 ms 85980 KB Output is correct
6 Correct 20 ms 85852 KB Output is correct
7 Correct 19 ms 85852 KB Output is correct
8 Correct 21 ms 85868 KB Output is correct
9 Correct 19 ms 85848 KB Output is correct
10 Correct 21 ms 85852 KB Output is correct
11 Correct 20 ms 85852 KB Output is correct
12 Correct 20 ms 85868 KB Output is correct
13 Correct 21 ms 85852 KB Output is correct
14 Correct 21 ms 85848 KB Output is correct
15 Correct 20 ms 85852 KB Output is correct
16 Correct 19 ms 85840 KB Output is correct
17 Correct 20 ms 86012 KB Output is correct
18 Correct 20 ms 85848 KB Output is correct
19 Correct 23 ms 85848 KB Output is correct
20 Correct 20 ms 85852 KB Output is correct
21 Correct 18 ms 85852 KB Output is correct
22 Correct 19 ms 85852 KB Output is correct
23 Correct 21 ms 85852 KB Output is correct
24 Correct 21 ms 85852 KB Output is correct
25 Correct 21 ms 85852 KB Output is correct
26 Correct 21 ms 85852 KB Output is correct
27 Correct 20 ms 85852 KB Output is correct
28 Correct 20 ms 85848 KB Output is correct
29 Correct 20 ms 85940 KB Output is correct
30 Correct 19 ms 85852 KB Output is correct
31 Correct 2734 ms 126692 KB Output is correct
32 Correct 96 ms 92428 KB Output is correct
33 Correct 602 ms 102616 KB Output is correct
34 Correct 2073 ms 109984 KB Output is correct
35 Correct 1838 ms 123104 KB Output is correct
36 Correct 682 ms 110272 KB Output is correct
37 Correct 618 ms 97232 KB Output is correct
38 Correct 384 ms 96308 KB Output is correct
39 Correct 368 ms 95568 KB Output is correct
40 Correct 335 ms 95616 KB Output is correct
41 Correct 708 ms 96132 KB Output is correct
42 Correct 760 ms 96204 KB Output is correct
43 Correct 73 ms 95520 KB Output is correct
44 Correct 711 ms 96184 KB Output is correct
45 Correct 578 ms 95948 KB Output is correct
46 Correct 425 ms 95788 KB Output is correct
47 Correct 346 ms 95256 KB Output is correct
48 Correct 314 ms 95220 KB Output is correct
49 Correct 479 ms 95320 KB Output is correct
50 Correct 650 ms 95992 KB Output is correct
51 Correct 424 ms 95344 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5024 ms 242968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 212768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 85844 KB Output is correct
2 Correct 19 ms 85856 KB Output is correct
3 Correct 18 ms 85848 KB Output is correct
4 Correct 18 ms 85852 KB Output is correct
5 Correct 20 ms 85980 KB Output is correct
6 Correct 20 ms 85852 KB Output is correct
7 Correct 19 ms 85852 KB Output is correct
8 Correct 21 ms 85868 KB Output is correct
9 Correct 19 ms 85848 KB Output is correct
10 Correct 21 ms 85852 KB Output is correct
11 Correct 20 ms 85852 KB Output is correct
12 Correct 20 ms 85868 KB Output is correct
13 Correct 21 ms 85852 KB Output is correct
14 Correct 21 ms 85848 KB Output is correct
15 Correct 20 ms 85852 KB Output is correct
16 Correct 19 ms 85840 KB Output is correct
17 Correct 20 ms 86012 KB Output is correct
18 Correct 20 ms 85848 KB Output is correct
19 Correct 23 ms 85848 KB Output is correct
20 Correct 20 ms 85852 KB Output is correct
21 Correct 18 ms 85852 KB Output is correct
22 Correct 19 ms 85852 KB Output is correct
23 Correct 21 ms 85852 KB Output is correct
24 Correct 21 ms 85852 KB Output is correct
25 Correct 21 ms 85852 KB Output is correct
26 Correct 21 ms 85852 KB Output is correct
27 Correct 20 ms 85852 KB Output is correct
28 Correct 20 ms 85848 KB Output is correct
29 Correct 20 ms 85940 KB Output is correct
30 Correct 19 ms 85852 KB Output is correct
31 Correct 2734 ms 126692 KB Output is correct
32 Correct 96 ms 92428 KB Output is correct
33 Correct 602 ms 102616 KB Output is correct
34 Correct 2073 ms 109984 KB Output is correct
35 Correct 1838 ms 123104 KB Output is correct
36 Correct 682 ms 110272 KB Output is correct
37 Correct 618 ms 97232 KB Output is correct
38 Correct 384 ms 96308 KB Output is correct
39 Correct 368 ms 95568 KB Output is correct
40 Correct 335 ms 95616 KB Output is correct
41 Correct 708 ms 96132 KB Output is correct
42 Correct 760 ms 96204 KB Output is correct
43 Correct 73 ms 95520 KB Output is correct
44 Correct 711 ms 96184 KB Output is correct
45 Correct 578 ms 95948 KB Output is correct
46 Correct 425 ms 95788 KB Output is correct
47 Correct 346 ms 95256 KB Output is correct
48 Correct 314 ms 95220 KB Output is correct
49 Correct 479 ms 95320 KB Output is correct
50 Correct 650 ms 95992 KB Output is correct
51 Correct 424 ms 95344 KB Output is correct
52 Correct 159 ms 101836 KB Output is correct
53 Correct 155 ms 98000 KB Output is correct
54 Correct 2148 ms 133392 KB Output is correct
55 Correct 537 ms 98104 KB Output is correct
56 Correct 438 ms 99532 KB Output is correct
57 Correct 672 ms 96828 KB Output is correct
58 Correct 580 ms 98292 KB Output is correct
59 Correct 488 ms 99324 KB Output is correct
60 Correct 724 ms 96964 KB Output is correct
61 Correct 71 ms 99344 KB Output is correct
62 Correct 158 ms 102016 KB Output is correct
63 Correct 1203 ms 118188 KB Output is correct
64 Correct 1539 ms 117268 KB Output is correct
65 Correct 1243 ms 102876 KB Output is correct
66 Correct 833 ms 96792 KB Output is correct
67 Correct 534 ms 95180 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 85844 KB Output is correct
2 Correct 19 ms 85856 KB Output is correct
3 Correct 18 ms 85848 KB Output is correct
4 Correct 18 ms 85852 KB Output is correct
5 Correct 20 ms 85980 KB Output is correct
6 Correct 20 ms 85852 KB Output is correct
7 Correct 19 ms 85852 KB Output is correct
8 Correct 21 ms 85868 KB Output is correct
9 Correct 19 ms 85848 KB Output is correct
10 Correct 21 ms 85852 KB Output is correct
11 Correct 20 ms 85852 KB Output is correct
12 Correct 20 ms 85868 KB Output is correct
13 Correct 21 ms 85852 KB Output is correct
14 Correct 21 ms 85848 KB Output is correct
15 Correct 20 ms 85852 KB Output is correct
16 Correct 19 ms 85840 KB Output is correct
17 Correct 20 ms 86012 KB Output is correct
18 Correct 20 ms 85848 KB Output is correct
19 Correct 23 ms 85848 KB Output is correct
20 Correct 20 ms 85852 KB Output is correct
21 Correct 18 ms 85852 KB Output is correct
22 Correct 19 ms 85852 KB Output is correct
23 Correct 21 ms 85852 KB Output is correct
24 Correct 21 ms 85852 KB Output is correct
25 Correct 21 ms 85852 KB Output is correct
26 Correct 21 ms 85852 KB Output is correct
27 Correct 20 ms 85852 KB Output is correct
28 Correct 20 ms 85848 KB Output is correct
29 Correct 20 ms 85940 KB Output is correct
30 Correct 19 ms 85852 KB Output is correct
31 Correct 2734 ms 126692 KB Output is correct
32 Correct 96 ms 92428 KB Output is correct
33 Correct 602 ms 102616 KB Output is correct
34 Correct 2073 ms 109984 KB Output is correct
35 Correct 1838 ms 123104 KB Output is correct
36 Correct 682 ms 110272 KB Output is correct
37 Correct 618 ms 97232 KB Output is correct
38 Correct 384 ms 96308 KB Output is correct
39 Correct 368 ms 95568 KB Output is correct
40 Correct 335 ms 95616 KB Output is correct
41 Correct 708 ms 96132 KB Output is correct
42 Correct 760 ms 96204 KB Output is correct
43 Correct 73 ms 95520 KB Output is correct
44 Correct 711 ms 96184 KB Output is correct
45 Correct 578 ms 95948 KB Output is correct
46 Correct 425 ms 95788 KB Output is correct
47 Correct 346 ms 95256 KB Output is correct
48 Correct 314 ms 95220 KB Output is correct
49 Correct 479 ms 95320 KB Output is correct
50 Correct 650 ms 95992 KB Output is correct
51 Correct 424 ms 95344 KB Output is correct
52 Execution timed out 5024 ms 242968 KB Time limit exceeded
53 Halted 0 ms 0 KB -