oj.uz

Submission #872718

# Submission time Handle Problem Language Result Execution time Memory
872718 2023-11-13T15:34:48 Z serifefedartar Road Construction (JOI21_road_construction) C++17
100 / 100
 5973 ms 34892 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 2e5 + 100;
#define int long long

vector<pair<int,int>> pnt;
vector<pair<int, pair<int,int>>> v;
vector<ll> ans;
ll N, K;
int manh(int i, int j) {
	return max(abs(pnt[i].f - pnt[j].f), abs(pnt[i].s - pnt[j].s));
}

bool check(ll mid, int type) {
	ll q = (ll)v.size(), r = 0;
	ll cnt = 0;

	tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> oset;
	for (int l = 0; l < q; l++) {
		while (r + 1 < q && v[r+1].f - v[l].f <= mid) {
			r++;
			for (int i = v[r].s.f; i <= v[r].s.s; i++)
				oset.insert({pnt[i].s, i});
		}

		for (int i = v[l].s.f; i <= v[l].s.s; i++)
			oset.erase({pnt[i].s, i});

		for (int i = v[l].s.f; i <= v[l].s.s; i++) {
			oset.insert({pnt[i].s, i});
			ll lPtr = oset.order_of_key(make_pair(pnt[i].s - mid, -1));
			ll rPtr = oset.order_of_key(make_pair(pnt[i].s + mid, 1e8)) - 1;
			cnt += rPtr - lPtr;
			if (type) {
				for (int j = lPtr; j <= rPtr; j++) {
					int no = (*oset.find_by_order(j)).s;
					if (no != i)
						ans.push_back(manh(i, no));
				}
			}
		}

		for (int i = v[l].s.f; i <= v[l].s.s; i++)
			oset.erase({pnt[i].s, i});
	}

	return (cnt >= K);
}

signed main() {
	fast
	cin >> N >> K;

	pnt = vector<pair<int,int>>(N);
	for (int i = 0; i < N; i++) {
		cin >> pnt[i].f >> pnt[i].s;
		int x = pnt[i].f + pnt[i].s;
		int y = pnt[i].f - pnt[i].s;
		pnt[i] = {x, y};
	}
	sort(pnt.begin(), pnt.end());

	for (int i = 0; i < N; i++) {
		int j = i;
		while (j < N && pnt[i].f == pnt[j].f)
			j++;
		v.push_back({pnt[i].f, {i, j-1}});
		i = j-1;
	}

	ll L = 1;
	ll R = 1e10;
	ll res = -1;
	while (R >= L) {
		ll mid = L + (R-L)/2;
		if (check(mid, 0)) {
			R = mid - 1;
			res = mid;
		} else
			L = mid + 1;
	}
	check(res, 1);

	sort(ans.begin(), ans.end());
	for (int i = 0; i < K; i++)
		cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5192 KB Output is correct
2 Correct 54 ms 5060 KB Output is correct
3 Correct 48 ms 5100 KB Output is correct
4 Correct 46 ms 5316 KB Output is correct
5 Correct 50 ms 3904 KB Output is correct
6 Correct 8 ms 600 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2553 ms 26924 KB Output is correct
2 Correct 2526 ms 26960 KB Output is correct
3 Correct 40 ms 5056 KB Output is correct
4 Correct 2476 ms 26732 KB Output is correct
5 Correct 3340 ms 26920 KB Output is correct
6 Correct 3274 ms 27064 KB Output is correct
7 Correct 2835 ms 26216 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3706 ms 25728 KB Output is correct
2 Correct 3674 ms 25784 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3194 ms 28656 KB Output is correct
5 Correct 4497 ms 25352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3706 ms 25728 KB Output is correct
2 Correct 3674 ms 25784 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3194 ms 28656 KB Output is correct
5 Correct 4497 ms 25352 KB Output is correct
6 Correct 3945 ms 30800 KB Output is correct
7 Correct 3855 ms 30952 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3846 ms 30448 KB Output is correct
11 Correct 3509 ms 28624 KB Output is correct
12 Correct 4481 ms 25276 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5192 KB Output is correct
2 Correct 54 ms 5060 KB Output is correct
3 Correct 48 ms 5100 KB Output is correct
4 Correct 46 ms 5316 KB Output is correct
5 Correct 50 ms 3904 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 2386 ms 16952 KB Output is correct
8 Correct 2203 ms 14632 KB Output is correct
9 Correct 45 ms 5100 KB Output is correct
10 Correct 1647 ms 16820 KB Output is correct
11 Correct 1288 ms 15296 KB Output is correct
12 Correct 1417 ms 15700 KB Output is correct
13 Correct 1766 ms 14028 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5192 KB Output is correct
2 Correct 54 ms 5060 KB Output is correct
3 Correct 48 ms 5100 KB Output is correct
4 Correct 46 ms 5316 KB Output is correct
5 Correct 50 ms 3904 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 2553 ms 26924 KB Output is correct
8 Correct 2526 ms 26960 KB Output is correct
9 Correct 40 ms 5056 KB Output is correct
10 Correct 2476 ms 26732 KB Output is correct
11 Correct 3340 ms 26920 KB Output is correct
12 Correct 3274 ms 27064 KB Output is correct
13 Correct 2835 ms 26216 KB Output is correct
14 Correct 3706 ms 25728 KB Output is correct
15 Correct 3674 ms 25784 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 3194 ms 28656 KB Output is correct
18 Correct 4497 ms 25352 KB Output is correct
19 Correct 3945 ms 30800 KB Output is correct
20 Correct 3855 ms 30952 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3846 ms 30448 KB Output is correct
24 Correct 3509 ms 28624 KB Output is correct
25 Correct 4481 ms 25276 KB Output is correct
26 Correct 2386 ms 16952 KB Output is correct
27 Correct 2203 ms 14632 KB Output is correct
28 Correct 45 ms 5100 KB Output is correct
29 Correct 1647 ms 16820 KB Output is correct
30 Correct 1288 ms 15296 KB Output is correct
31 Correct 1417 ms 15700 KB Output is correct
32 Correct 1766 ms 14028 KB Output is correct
33 Correct 5973 ms 32776 KB Output is correct
34 Correct 5842 ms 32776 KB Output is correct
35 Correct 4638 ms 31372 KB Output is correct
36 Correct 4189 ms 34880 KB Output is correct
37 Correct 4108 ms 34892 KB Output is correct
38 Correct 4818 ms 25636 KB Output is correct