oj.uz

답안 #870115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870115 2023-11-07T02:05:35 Z NK_ Road Construction (JOI21_road_construction) C++17
33 / 100
 3345 ms 31144 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;
				if (t) for(int x = li; x <= ri; x++) {
					int j = (*B.find_by_order(x)).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

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 5184 KB Output is correct
2 Correct 49 ms 5432 KB Output is correct
3 Correct 48 ms 5244 KB Output is correct
4 Correct 43 ms 5256 KB Output is correct
5 Incorrect 46 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1597 ms 27072 KB Output is correct
2 Correct 1522 ms 26916 KB Output is correct
3 Correct 45 ms 4892 KB Output is correct
4 Correct 1473 ms 26732 KB Output is correct
5 Correct 1487 ms 27032 KB Output is correct
6 Correct 1494 ms 27060 KB Output is correct
7 Correct 1589 ms 26148 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3215 ms 25892 KB Output is correct
2 Correct 3062 ms 30980 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1472 ms 28772 KB Output is correct
5 Correct 3345 ms 25384 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3215 ms 25892 KB Output is correct
2 Correct 3062 ms 30980 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1472 ms 28772 KB Output is correct
5 Correct 3345 ms 25384 KB Output is correct
6 Correct 3240 ms 31004 KB Output is correct
7 Correct 3145 ms 30976 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3228 ms 31144 KB Output is correct
11 Correct 1491 ms 28836 KB Output is correct
12 Correct 3064 ms 25564 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 5184 KB Output is correct
2 Correct 49 ms 5432 KB Output is correct
3 Correct 48 ms 5244 KB Output is correct
4 Correct 43 ms 5256 KB Output is correct
5 Incorrect 46 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 5184 KB Output is correct
2 Correct 49 ms 5432 KB Output is correct
3 Correct 48 ms 5244 KB Output is correct
4 Correct 43 ms 5256 KB Output is correct
5 Incorrect 46 ms 4556 KB Output isn't correct
6 Halted 0 ms 0 KB -