oj.uz

Submission #716762

# Submission time Handle Problem Language Result Execution time Memory
716762 2023-03-31T03:42:21 Z pavement Road Construction (JOI21_road_construction) C++17
100 / 100
 5905 ms 112488 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, X[250005], Y[250005], A[250005], B[250005], ft[250005], SB[250005];
ii T[250005];
vector<int> out, vec;

int ls(int x) { return x & -x; }

int conv(int p) {
	auto it = upper_bound(SB + 1, SB + 1 + N, p);
	return it - SB - 1;
}

int conv2(int p) {
	auto it = lower_bound(SB + 1, SB + 1 + N, p);
	return it - SB;
}

int qry(int p) {
	p = conv(p);
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

void upd(int p, int v) {
	p = conv(p);
	for (; p <= N; p += ls(p)) ft[p] += v;
}

struct node {
	node *left, *right;
	int S, E, ptr;
	vector<int> val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void del(int p) {
		ptr++;
		if (S == E) return;
		int M = (S + E) >> 1;
		if (p <= M) left->del(p);
		else right->del(p);
	}
	void upd(int p, int v) {
		val.pb(v);
		if (S == E) return;
		int M = (S + E) >> 1;
		if (p <= M) left->upd(p, v);
		else right->upd(p, v);
	}
	void find_all(int l, int r) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			for (int i = ptr; i < (int)val.size(); i++) {
				vec.pb(val[i]);
			}
			return;
		}
		left->find_all(l, r);
		right->find_all(l, r);
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
		A[i] = (X[i] + Y[i]);
		B[i] = (X[i] - Y[i]);
		SB[i] = B[i];
		T[i] = mp(A[i], B[i]);
	}
	sort(T + 1, T + 1 + N);
	sort(SB + 1, SB + 1 + N);
	for (int i = 1; i <= N; i++) {
		tie(A[i], B[i]) = T[i];
	}
	int lo = 0, hi = (int)1e10, ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2, cnt = 0;
		for (int i = 1; i <= N; i++) {
			ft[i] = 0;
		}
		for (int i = 1, ptr = 1; i <= N; i++) {
			while (A[i] - A[ptr] > mid) {
				assert(ptr < i);
				upd(B[ptr], -1);
				ptr++;
			}
			cnt += qry(B[i] + mid) - qry(B[i] - mid - 1);
			upd(B[i], 1);
		}
		if (cnt >= K) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	root = new node(1, N);
	for (int i = 1, ptr = 1; i <= N; i++) {
		while (A[i] - A[ptr] > ans - 1) {
			assert(ptr < i);
			root->del(conv(B[ptr]));
			ptr++;
		}
		vec.clear();
		root->find_all(conv2(B[i] - (ans - 1)), conv(B[i] + (ans - 1)));
		for (auto j : vec) {
			out.eb(max(llabs(A[i] - A[j]), llabs(B[i] - B[j])));
		}
		root->upd(conv(B[i]), i);
	}
	sort(out.begin(), out.end());
	for (auto i : out) cout << i << '\n';
	for (int i = 0; i < K - (int)out.size(); i++) cout << ans << '\n';
}

Compilation message

road_construction.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5316 KB Output is correct
2 Correct 46 ms 5284 KB Output is correct
3 Correct 40 ms 5236 KB Output is correct
4 Correct 44 ms 5360 KB Output is correct
5 Correct 44 ms 4168 KB Output is correct
6 Correct 5 ms 672 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2325 ms 109572 KB Output is correct
2 Correct 2315 ms 109532 KB Output is correct
3 Correct 40 ms 5084 KB Output is correct
4 Correct 2207 ms 109276 KB Output is correct
5 Correct 2193 ms 109336 KB Output is correct
6 Correct 2178 ms 109572 KB Output is correct
7 Correct 2202 ms 108884 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5110 ms 108312 KB Output is correct
2 Correct 5077 ms 108312 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2176 ms 106128 KB Output is correct
5 Correct 4160 ms 108056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5110 ms 108312 KB Output is correct
2 Correct 5077 ms 108312 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2176 ms 106128 KB Output is correct
5 Correct 4160 ms 108056 KB Output is correct
6 Correct 5177 ms 108312 KB Output is correct
7 Correct 5445 ms 108316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5101 ms 108128 KB Output is correct
11 Correct 2161 ms 106172 KB Output is correct
12 Correct 4173 ms 108056 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5316 KB Output is correct
2 Correct 46 ms 5284 KB Output is correct
3 Correct 40 ms 5236 KB Output is correct
4 Correct 44 ms 5360 KB Output is correct
5 Correct 44 ms 4168 KB Output is correct
6 Correct 5 ms 672 KB Output is correct
7 Correct 2086 ms 48824 KB Output is correct
8 Correct 2098 ms 48948 KB Output is correct
9 Correct 40 ms 5364 KB Output is correct
10 Correct 1967 ms 47804 KB Output is correct
11 Correct 1734 ms 47384 KB Output is correct
12 Correct 1289 ms 46184 KB Output is correct
13 Correct 1488 ms 44708 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5316 KB Output is correct
2 Correct 46 ms 5284 KB Output is correct
3 Correct 40 ms 5236 KB Output is correct
4 Correct 44 ms 5360 KB Output is correct
5 Correct 44 ms 4168 KB Output is correct
6 Correct 5 ms 672 KB Output is correct
7 Correct 2325 ms 109572 KB Output is correct
8 Correct 2315 ms 109532 KB Output is correct
9 Correct 40 ms 5084 KB Output is correct
10 Correct 2207 ms 109276 KB Output is correct
11 Correct 2193 ms 109336 KB Output is correct
12 Correct 2178 ms 109572 KB Output is correct
13 Correct 2202 ms 108884 KB Output is correct
14 Correct 5110 ms 108312 KB Output is correct
15 Correct 5077 ms 108312 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2176 ms 106128 KB Output is correct
18 Correct 4160 ms 108056 KB Output is correct
19 Correct 5177 ms 108312 KB Output is correct
20 Correct 5445 ms 108316 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 5101 ms 108128 KB Output is correct
24 Correct 2161 ms 106172 KB Output is correct
25 Correct 4173 ms 108056 KB Output is correct
26 Correct 2086 ms 48824 KB Output is correct
27 Correct 2098 ms 48948 KB Output is correct
28 Correct 40 ms 5364 KB Output is correct
29 Correct 1967 ms 47804 KB Output is correct
30 Correct 1734 ms 47384 KB Output is correct
31 Correct 1289 ms 46184 KB Output is correct
32 Correct 1488 ms 44708 KB Output is correct
33 Correct 5849 ms 112404 KB Output is correct
34 Correct 5905 ms 112488 KB Output is correct
35 Correct 5306 ms 110852 KB Output is correct
36 Correct 3162 ms 100776 KB Output is correct
37 Correct 3361 ms 100572 KB Output is correct
38 Correct 4305 ms 111804 KB Output is correct