oj.uz

Submission #870127

# Submission time Handle Problem Language Result Execution time Memory
870127 2023-11-07T02:23:39 Z NK_ Road Construction (JOI21_road_construction) C++17
33 / 100
 3064 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 = [&](const pl &a, const pl &b) -> ll { 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 = {}; 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(l <= r && (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++) {
				int li = B.order_of_key(mp(A[i].s - d, -MOD));
				int ri = B.order_of_key(mp(A[i].s + d, MOD)) - 1;

				ans += ri - li;
				if (t) for(int x = li; x <= ri; x++) {
					int j = (*B.find_by_order(x)).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 = 5LL * 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));
	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 47 ms 5180 KB Output is correct
2 Correct 47 ms 5184 KB Output is correct
3 Correct 40 ms 5144 KB Output is correct
4 Correct 40 ms 6784 KB Output is correct
5 Incorrect 44 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 1460 ms 26984 KB Output is correct
2 Correct 1443 ms 26920 KB Output is correct
3 Correct 36 ms 4892 KB Output is correct
4 Correct 1397 ms 26668 KB Output is correct
5 Correct 1425 ms 27320 KB Output is correct
6 Correct 1422 ms 27060 KB Output is correct
7 Correct 1463 ms 26508 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 23932 KB Output is correct
2 Correct 2698 ms 23676 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1379 ms 25980 KB Output is correct
5 Correct 3035 ms 20040 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 23932 KB Output is correct
2 Correct 2698 ms 23676 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1379 ms 25980 KB Output is correct
5 Correct 3035 ms 20040 KB Output is correct
6 Correct 2824 ms 23684 KB Output is correct
7 Correct 2794 ms 23740 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2721 ms 23240 KB Output is correct
11 Correct 1371 ms 26300 KB Output is correct
12 Correct 3064 ms 20040 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5180 KB Output is correct
2 Correct 47 ms 5184 KB Output is correct
3 Correct 40 ms 5144 KB Output is correct
4 Correct 40 ms 6784 KB Output is correct
5 Incorrect 44 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 47 ms 5180 KB Output is correct
2 Correct 47 ms 5184 KB Output is correct
3 Correct 40 ms 5144 KB Output is correct
4 Correct 40 ms 6784 KB Output is correct
5 Incorrect 44 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -