oj.uz

답안 #870124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870124 2023-11-07T02:20:52 Z NK_ Road Construction (JOI21_road_construction) C++17
33 / 100
 3570 ms 27164 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; 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 = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5152 KB Output is correct
2 Correct 44 ms 5184 KB Output is correct
3 Correct 37 ms 5172 KB Output is correct
4 Correct 37 ms 5756 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1514 ms 26912 KB Output is correct
2 Correct 1505 ms 27064 KB Output is correct
3 Correct 33 ms 4896 KB Output is correct
4 Correct 1442 ms 26668 KB Output is correct
5 Correct 1512 ms 26916 KB Output is correct
6 Correct 1504 ms 27164 KB Output is correct
7 Correct 1547 ms 26148 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2991 ms 23992 KB Output is correct
2 Correct 2717 ms 23676 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1488 ms 25896 KB Output is correct
5 Correct 3570 ms 20044 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2991 ms 23992 KB Output is correct
2 Correct 2717 ms 23676 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1488 ms 25896 KB Output is correct
5 Correct 3570 ms 20044 KB Output is correct
6 Correct 3235 ms 23684 KB Output is correct
7 Correct 3143 ms 23724 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2996 ms 23420 KB Output is correct
11 Correct 1453 ms 25792 KB Output is correct
12 Correct 3405 ms 20048 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5152 KB Output is correct
2 Correct 44 ms 5184 KB Output is correct
3 Correct 37 ms 5172 KB Output is correct
4 Correct 37 ms 5756 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

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5152 KB Output is correct
2 Correct 44 ms 5184 KB Output is correct
3 Correct 37 ms 5172 KB Output is correct
4 Correct 37 ms 5756 KB Output is correct
5 Incorrect 41 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -