oj.uz

답안 #387324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387324 2021-04-08T09:12:55 Z SeDunion Road Construction (JOI21_road_construction) C++17
100 / 100
 4634 ms 21468 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 250000 + 6;

ll X[N], Y[N];

int p[N];
int n, k, x[N], y[N];
vector<ll>xs,ys;

int F[N];
void upd(int pos, int v) {
	while (pos < N) {
		F[pos] += v;
		pos |= pos + 1;
	}
}
int get(int pos) {
	int r = 0;
	while (pos >= 0) {
		r += F[pos];
		pos &= pos + 1, pos--;
	}
	return r;
}

bool check(ll M) {
	int res = 0;
	int l = 1;
	for (int i = 0 ; i < N ; ++ i) F[i] = 0;
	for (int i = 1 ; i <= n ; ++ i) {
		while (l < i && X[p[i]] - X[p[l]] >= M) {
			upd(y[p[l]], -1);
			l++;
		}
		int sx = lower_bound(ys.begin(), ys.end(), Y[p[i]] - M + 1) - ys.begin();
		int ex = upper_bound(ys.begin(), ys.end(), Y[p[i]] + M - 1) - ys.begin() - 1;
		res += get(ex) - get(sx - 1);
		if (res >= k) break;
		upd(y[p[i]], +1);
	}
	while (l <= n) upd(y[p[l]], -1), ++l;
	return res >= k;
}

vector<ll>ANS;

void restore(ll M) {
	set<pair<ll,ll>>S = {{Y[p[1]], X[p[1]]}};
	int l = 1;
	for (int i = 2 ; i <= n ; ++ i) {
		while (l < i && X[p[i]] - X[p[l]] >= M) {
			S.erase({Y[p[l]], X[p[l]]});
			l++;
		}
		auto st = S.lower_bound(pair{Y[p[i]] - M + 1, -1e10});
		for (; st != S.end() ; ++ st) {
			if (max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])) < M) {
				ANS.emplace_back(max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])));
			} else break;
		}
		S.insert({Y[p[i]], X[p[i]]});
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1 ; i <= n ; ++ i) {
		ll a, b;
		cin >> a >> b;
		X[i] = a + b, Y[i] = a - b;
		xs.emplace_back(X[i]), ys.emplace_back(Y[i]);
	}
	sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
	for (int i = 1 ; i <= n ; ++ i) {
		x[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
		y[i] = lower_bound(ys.begin(), ys.end(), Y[i]) - ys.begin();
	}
	for (int i = 1 ; i <= n ; ++ i) {
		p[i] = i;
	}
	sort(p + 1, p + 1 + n, [](int i, int j) {
		return X[i] < X[j];
	});
	ll L = 1, R = ll(1e10);
	ll ans = -1;
	while (L <= R) {
		ll M = (L + R) / 2;
		int res = check(M);
		if (!res) { // ? < k
			ans = M;
			L = M + 1;
		} else {
			R = M - 1;
		}
	}
	assert(ans != -1);
	restore(ans);
	sort(ANS.begin(), ANS.end());
	for (ll i : ANS) cout << i << endl;;
	int cnt = ANS.size();
	for (; cnt < k ; ++cnt) {
		cout << ans << "\n";
	}
	cout << endl;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 6380 KB Output is correct
2 Correct 584 ms 6252 KB Output is correct
3 Correct 586 ms 6220 KB Output is correct
4 Correct 583 ms 6252 KB Output is correct
5 Correct 572 ms 4972 KB Output is correct
6 Correct 9 ms 1388 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2059 ms 18620 KB Output is correct
2 Correct 1936 ms 18636 KB Output is correct
3 Correct 580 ms 6244 KB Output is correct
4 Correct 1752 ms 18340 KB Output is correct
5 Correct 1718 ms 18580 KB Output is correct
6 Correct 1685 ms 18420 KB Output is correct
7 Correct 1468 ms 18384 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1844 ms 17360 KB Output is correct
2 Correct 2271 ms 17488 KB Output is correct
3 Correct 6 ms 1388 KB Output is correct
4 Correct 859 ms 15348 KB Output is correct
5 Correct 1220 ms 17616 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1844 ms 17360 KB Output is correct
2 Correct 2271 ms 17488 KB Output is correct
3 Correct 6 ms 1388 KB Output is correct
4 Correct 859 ms 15348 KB Output is correct
5 Correct 1220 ms 17616 KB Output is correct
6 Correct 2740 ms 17360 KB Output is correct
7 Correct 2669 ms 17436 KB Output is correct
8 Correct 6 ms 1536 KB Output is correct
9 Correct 6 ms 1388 KB Output is correct
10 Correct 2699 ms 17488 KB Output is correct
11 Correct 937 ms 15312 KB Output is correct
12 Correct 1296 ms 17684 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 6380 KB Output is correct
2 Correct 584 ms 6252 KB Output is correct
3 Correct 586 ms 6220 KB Output is correct
4 Correct 583 ms 6252 KB Output is correct
5 Correct 572 ms 4972 KB Output is correct
6 Correct 9 ms 1388 KB Output is correct
7 Correct 1784 ms 11884 KB Output is correct
8 Correct 1719 ms 11884 KB Output is correct
9 Correct 572 ms 6292 KB Output is correct
10 Correct 1539 ms 11124 KB Output is correct
11 Correct 1274 ms 11240 KB Output is correct
12 Correct 563 ms 9944 KB Output is correct
13 Correct 1006 ms 10504 KB Output is correct

Subtask #6
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 6380 KB Output is correct
2 Correct 584 ms 6252 KB Output is correct
3 Correct 586 ms 6220 KB Output is correct
4 Correct 583 ms 6252 KB Output is correct
5 Correct 572 ms 4972 KB Output is correct
6 Correct 9 ms 1388 KB Output is correct
7 Correct 2059 ms 18620 KB Output is correct
8 Correct 1936 ms 18636 KB Output is correct
9 Correct 580 ms 6244 KB Output is correct
10 Correct 1752 ms 18340 KB Output is correct
11 Correct 1718 ms 18580 KB Output is correct
12 Correct 1685 ms 18420 KB Output is correct
13 Correct 1468 ms 18384 KB Output is correct
14 Correct 1844 ms 17360 KB Output is correct
15 Correct 2271 ms 17488 KB Output is correct
16 Correct 6 ms 1388 KB Output is correct
17 Correct 859 ms 15348 KB Output is correct
18 Correct 1220 ms 17616 KB Output is correct
19 Correct 2740 ms 17360 KB Output is correct
20 Correct 2669 ms 17436 KB Output is correct
21 Correct 6 ms 1536 KB Output is correct
22 Correct 6 ms 1388 KB Output is correct
23 Correct 2699 ms 17488 KB Output is correct
24 Correct 937 ms 15312 KB Output is correct
25 Correct 1296 ms 17684 KB Output is correct
26 Correct 1784 ms 11884 KB Output is correct
27 Correct 1719 ms 11884 KB Output is correct
28 Correct 572 ms 6292 KB Output is correct
29 Correct 1539 ms 11124 KB Output is correct
30 Correct 1274 ms 11240 KB Output is correct
31 Correct 563 ms 9944 KB Output is correct
32 Correct 1006 ms 10504 KB Output is correct
33 Correct 4634 ms 21348 KB Output is correct
34 Correct 4579 ms 21468 KB Output is correct
35 Correct 3929 ms 20664 KB Output is correct
36 Correct 1558 ms 19396 KB Output is correct
37 Correct 1442 ms 19448 KB Output is correct
38 Correct 1839 ms 20560 KB Output is correct