oj.uz

Submission #870119

# Submission time Handle Problem Language Result Execution time Memory
870119 2023-11-07T02:09:44 Z NK_ Road Construction (JOI21_road_construction) C++17
33 / 100
 3671 ms 27320 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
using str = string;
 

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
template<class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	// rotate 45 (x, y) -> (x + y, x - y)
	// Change Manhattan Distance to C. Distance (max(∆x, ∆y))

	int N, K; cin >> N >> K;
	vpl A(N); for(auto& x : A) cin >> x.f >> x.s;

	for(auto& x : A) x = mp(x.f + x.s, x.f - x.s);
	sort(begin(A), end(A));

	V<array<ll, 3>> R; 
	for(int i = 0; i < N; i++) {
		int j = i;
		while(j < N && A[i].f == A[j].f) j++;
		R.pb(array<ll, 3>{A[i].f, i, j - 1});
		i = j - 1;
	}

	int M = sz(R);

	auto dist = [&](pl a, pl b) { return max(abs(a.f - b.f), abs(a.s - b.s)); };

	iset<pl> B; vl ANS;

	auto get = [&](ll d, int t) {
		// d -> distance within
		// t -> get pairs

		int Q = 0;
		B.clear(); ll ans = 0; vl res;
		for(int l = 0, r = 0; r < M; r++) {
			// ADD r
			for(int i = R[r][1]; i <= R[r][2]; i++) B.insert(mp(A[i].s, i));

			// REM l(s)
			while((R[r][0] - R[l][0]) > d) {
				for(int i = R[l][1]; i <= R[l][2]; i++) B.erase(mp(A[i].s, i));
				l++;
			}

			// COUNT PAIRS (for people in r);
			for(int i = R[r][1]; i <= R[r][2]; i++) {
				ll lx = A[i].s - d, rx = A[i].s + d;

				int li = B.order_of_key(mp(lx, -MOD)), ri = B.order_of_key(mp(rx, MOD)) - 1;

				ans += ri - li; auto it = B.find_by_order(li);
				if (t) for(int x = li; x <= ri; x++, it = next(it)) {
					int j = (*it).s;
					if (i == j) continue;
					Q++;

					// cout << i << " " << j << " => " << dist(A[i], A[j]) << nl;
					// cout << A[i].f << " " << A[i].s << nl;
					// cout << A[j].f << " " << A[j].s << nl;

					res.pb(dist(A[i], A[j]));
				}
			}
		}

		assert(Q <= 2 * K);

		if (t) ANS = res;

		// cout << d << " => " << ans << endl;

		return ans;
	};


	ll lo = 0, hi = 10LL * MOD;
	while(lo < hi) {
		ll mid = (lo + hi) / 2;
		if (get(mid, 0) > K) hi = mid;
		else lo = mid + 1;
	}

	get(lo - 1, 1); sort(begin(ANS), end(ANS));
	// cout << sz(ANS) << nl << nl;
	while(sz(ANS) < K) ANS.pb(lo);

	for(auto& x : ANS) cout << x << nl;

	exit(0-0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5148 KB Output is correct
2 Correct 46 ms 5148 KB Output is correct
3 Correct 38 ms 5216 KB Output is correct
4 Correct 41 ms 5240 KB Output is correct
5 Incorrect 42 ms 4552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1592 ms 26920 KB Output is correct
2 Correct 1595 ms 27320 KB Output is correct
3 Correct 39 ms 4888 KB Output is correct
4 Correct 1545 ms 26748 KB Output is correct
5 Correct 1618 ms 26924 KB Output is correct
6 Correct 1548 ms 26976 KB Output is correct
7 Correct 1664 ms 26292 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3248 ms 25896 KB Output is correct
2 Correct 3176 ms 25784 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1492 ms 25996 KB Output is correct
5 Correct 3671 ms 20044 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3248 ms 25896 KB Output is correct
2 Correct 3176 ms 25784 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1492 ms 25996 KB Output is correct
5 Correct 3671 ms 20044 KB Output is correct
6 Correct 3362 ms 25892 KB Output is correct
7 Correct 3303 ms 25888 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3317 ms 25672 KB Output is correct
11 Correct 1485 ms 25888 KB Output is correct
12 Correct 3508 ms 20036 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5148 KB Output is correct
2 Correct 46 ms 5148 KB Output is correct
3 Correct 38 ms 5216 KB Output is correct
4 Correct 41 ms 5240 KB Output is correct
5 Incorrect 42 ms 4552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5148 KB Output is correct
2 Correct 46 ms 5148 KB Output is correct
3 Correct 38 ms 5216 KB Output is correct
4 Correct 41 ms 5240 KB Output is correct
5 Incorrect 42 ms 4552 KB Output isn't correct
6 Halted 0 ms 0 KB -