oj.uz

Submission #870116

# Submission time Handle Problem Language Result Execution time Memory
870116 2023-11-07T02:07:20 Z NK_ Road Construction (JOI21_road_construction) C++17
33 / 100
 3671 ms 27336 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({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

		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;

					// 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(sz(res) <= 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 5152 KB Output is correct
2 Correct 45 ms 5140 KB Output is correct
3 Correct 37 ms 5148 KB Output is correct
4 Correct 37 ms 6780 KB Output is correct
5 Incorrect 41 ms 4556 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 1642 ms 26992 KB Output is correct
2 Correct 1590 ms 27336 KB Output is correct
3 Correct 34 ms 4908 KB Output is correct
4 Correct 1543 ms 26912 KB Output is correct
5 Correct 1556 ms 26924 KB Output is correct
6 Correct 1566 ms 27056 KB Output is correct
7 Correct 1625 ms 26200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3128 ms 26084 KB Output is correct
2 Correct 3130 ms 25912 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1492 ms 26060 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 3128 ms 26084 KB Output is correct
2 Correct 3130 ms 25912 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1492 ms 26060 KB Output is correct
5 Correct 3671 ms 20044 KB Output is correct
6 Correct 3016 ms 25896 KB Output is correct
7 Correct 3232 ms 25896 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3020 ms 25432 KB Output is correct
11 Correct 1499 ms 25892 KB Output is correct
12 Correct 3511 ms 20044 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5152 KB Output is correct
2 Correct 45 ms 5140 KB Output is correct
3 Correct 37 ms 5148 KB Output is correct
4 Correct 37 ms 6780 KB Output is correct
5 Incorrect 41 ms 4556 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 5152 KB Output is correct
2 Correct 45 ms 5140 KB Output is correct
3 Correct 37 ms 5148 KB Output is correct
4 Correct 37 ms 6780 KB Output is correct
5 Incorrect 41 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -