oj.uz

Submission #392962

# Submission time Handle Problem Language Result Execution time Memory
392962 2021-04-22T12:41:39 Z Mlxa Road Construction (JOI21_road_construction) C++14
100 / 100
 8750 ms 49932 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
#define int ll
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()

const int N = 1 << 18, INF = 1e18;
const int OPEN = -1, QUERY = 0, CLOSE = 1;

template<class T>
using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, k;
pair<int, int> p[N];
iset<pair<int, int>> q;

int query(int c) {
	vector<tuple<int, int, int>> scan;
	for (int i = 0; i < n; ++i) {
		scan.emplace_back(p[i].x - c,  OPEN, p[i].y);
		scan.emplace_back(p[i].x,     QUERY, p[i].y);
		scan.emplace_back(p[i].x + c, CLOSE, p[i].y);
	}
	sort(all(scan));
	q.clear();
	int answer = 0;
	for (auto e : scan) {
		int x, t, y;
		tie(x, t, y) = e;
		if (t == OPEN) {
			q.insert(mp(y, x + c));
		} else if (t == CLOSE) {
			q.erase(mp(y, x - c));
		} else {
			int lef = q.order_of_key(mp(y - c, -INF)),
				rig = q.order_of_key(mp(y + c, +INF));
			answer += rig - lef - 1;
		}
	}
	assert(answer % 2 == 0);
	return answer /= 2;
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0); 
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y;
		int nx = p[i].x + p[i].y;
		int ny = p[i].x - p[i].y;
		p[i].x = nx;
		p[i].y = ny;
		// cout << i << " " << nx << " " << ny << endl;
	}
	sort(p, p + n);
	int lef = -1, rig = (int)1e10;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (query(mid) < k) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	int c = lef;
	vector<int> answer;
	vector<tuple<int, int, int>> scan;
	for (int i = 0; i < n; ++i) {
		scan.emplace_back(p[i].x - c,  OPEN, p[i].y);
		scan.emplace_back(p[i].x,     QUERY, p[i].y);
		scan.emplace_back(p[i].x + c, CLOSE, p[i].y);
	}
	sort(all(scan));
	q.clear();
	for (auto e : scan) {
		int x, t, y;
		tie(x, t, y) = e;
		if (t == OPEN) {
			q.insert(mp(y, x + c));
		} else if (t == CLOSE) {
			q.erase(mp(y, x - c));
		} else {
			auto le = q.lower_bound(mp(y - c, -INF)),
				 ri = q.upper_bound(mp(y + c, +INF));
			for (auto it = le; it != ri; ++it) {
				int px = it->y, py = it->x, d = max(abs(px - x), abs(py - y));
				if (!d) {
					continue;
				}
				answer.push_back(d);
			}
		}
	}
	sort(all(answer));
	for (int i = 0; i + 1 < (int)answer.size(); i += 2) {
		assert(answer[i] == answer[i + 1]);
	}
	for (int i = 0; i < k; ++i) {
		if (2 * i < (int)answer.size()) {
			cout << answer[2 * i] << "\n";
		} else {
			cout << rig << "\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7188 KB Output is correct
2 Correct 104 ms 7164 KB Output is correct
3 Correct 91 ms 7056 KB Output is correct
4 Correct 89 ms 7084 KB Output is correct
5 Correct 89 ms 5964 KB Output is correct
6 Correct 16 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4879 ms 49312 KB Output is correct
2 Correct 4825 ms 49292 KB Output is correct
3 Correct 81 ms 6920 KB Output is correct
4 Correct 4634 ms 49276 KB Output is correct
5 Correct 5205 ms 47640 KB Output is correct
6 Correct 5302 ms 47676 KB Output is correct
7 Correct 5085 ms 49364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6048 ms 49552 KB Output is correct
2 Correct 6235 ms 49048 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 5155 ms 48760 KB Output is correct
5 Correct 6851 ms 48008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6048 ms 49552 KB Output is correct
2 Correct 6235 ms 49048 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 5155 ms 48760 KB Output is correct
5 Correct 6851 ms 48008 KB Output is correct
6 Correct 6934 ms 49160 KB Output is correct
7 Correct 6513 ms 48900 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 6600 ms 49156 KB Output is correct
11 Correct 5179 ms 47520 KB Output is correct
12 Correct 6926 ms 47744 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7188 KB Output is correct
2 Correct 104 ms 7164 KB Output is correct
3 Correct 91 ms 7056 KB Output is correct
4 Correct 89 ms 7084 KB Output is correct
5 Correct 89 ms 5964 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 3202 ms 23224 KB Output is correct
8 Correct 3233 ms 23300 KB Output is correct
9 Correct 90 ms 7168 KB Output is correct
10 Correct 2699 ms 22540 KB Output is correct
11 Correct 2048 ms 22392 KB Output is correct
12 Correct 2447 ms 23288 KB Output is correct
13 Correct 2770 ms 22008 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7188 KB Output is correct
2 Correct 104 ms 7164 KB Output is correct
3 Correct 91 ms 7056 KB Output is correct
4 Correct 89 ms 7084 KB Output is correct
5 Correct 89 ms 5964 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 4879 ms 49312 KB Output is correct
8 Correct 4825 ms 49292 KB Output is correct
9 Correct 81 ms 6920 KB Output is correct
10 Correct 4634 ms 49276 KB Output is correct
11 Correct 5205 ms 47640 KB Output is correct
12 Correct 5302 ms 47676 KB Output is correct
13 Correct 5085 ms 49364 KB Output is correct
14 Correct 6048 ms 49552 KB Output is correct
15 Correct 6235 ms 49048 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 5155 ms 48760 KB Output is correct
18 Correct 6851 ms 48008 KB Output is correct
19 Correct 6934 ms 49160 KB Output is correct
20 Correct 6513 ms 48900 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 6600 ms 49156 KB Output is correct
24 Correct 5179 ms 47520 KB Output is correct
25 Correct 6926 ms 47744 KB Output is correct
26 Correct 3202 ms 23224 KB Output is correct
27 Correct 3233 ms 23300 KB Output is correct
28 Correct 90 ms 7168 KB Output is correct
29 Correct 2699 ms 22540 KB Output is correct
30 Correct 2048 ms 22392 KB Output is correct
31 Correct 2447 ms 23288 KB Output is correct
32 Correct 2770 ms 22008 KB Output is correct
33 Correct 8730 ms 49060 KB Output is correct
34 Correct 8750 ms 49932 KB Output is correct
35 Correct 7614 ms 49908 KB Output is correct
36 Correct 6610 ms 49400 KB Output is correct
37 Correct 6597 ms 49600 KB Output is correct
38 Correct 6941 ms 48824 KB Output is correct