oj.uz

Submission #600275

# Submission time Handle Problem Language Result Execution time Memory
600275 2022-07-20T16:02:22 Z valerikk Road Construction (JOI21_road_construction) C++17
100 / 100
 5445 ms 957188 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2.5e5 + 15;
const int INF = 2e9 + 1;

struct node {
	node *l, *r;
	pair<int, int> mn;

	node(node *l_, node *r_, pair<int, int> mn_) : l(l_), r(r_), mn(mn_) {}
};

node *copy(node *t) {
	return new node(t->l, t->r, t->mn);
}

node *build(int tl, int tr) {
	if (tr - tl == 1) {
		return new node(0, 0, {INF, INF});
	}
	int tm = (tl + tr) / 2;
	return new node(build(tl, tm), build(tm, tr), {INF, INF});
}

pair<int, int> get(node *t, int tl, int tr, int l, int r) {
	if (tl >= r || tr <= l) {
		return {INF, INF};
	}
	if (tl >= l && tr <= r) {
		return t->mn;
	}
	int tm = (tl + tr) / 2;
	return min(get(t->l, tl, tm, l, r), get(t->r, tm, tr, l, r));
}

void update(node *&t, int tl, int tr, int pos, pair<int, int> mn) {
	t = copy(t);
	if (tr - tl == 1) {
		t->mn = mn;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm) {
		update(t->l, tl, tm, pos, mn);
	} else {
		update(t->r, tm, tr, pos, mn);
	}
	t->mn = min(t->l->mn, t->r->mn);
}

int n, k;
int x[N], y[N];
vector<pair<long long, pair<int, int>>> D;
node *t[N];
int ordx[N], ordy[N];
int posx[N], posy[N];
int ry[N];

void go(int fx, int fy) {
	// cout << "--- " << fx << " " << fy << " ---\n";
	iota(ordx, ordx + n, 0);
	iota(ordy, ordy + n, 0);
	sort(ordx, ordx + n, [&](int i, int j) {
		return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]) || (x[i] == x[j] && y[i] == y[j] && i < j);
	});
	sort(ordy, ordy + n, [&](int i, int j) {
		return y[i] < y[j] || (y[i] == y[j] && x[i] < x[j]) || (y[i] == y[j] && x[i] == x[j] && i < j);
	});
	for (int i = 0; i < n; ++i) {
		posx[ordx[i]] = i;
		posy[ordy[i]] = i;
	}
	node *cur = build(0, n);
	for (int i = 0, j = 0; i < n; ++i) {	
		while (x[ordx[j]] <= x[ordx[i]] - fx && j < i) {
			int id = ordx[j];
			update(cur, 0, n, posy[id], {-x[id] - y[id], posy[id]});
			++j;
		}
		t[ordx[i]] = cur;
	}
	for (int i = 0, j = 0; i < n; ++i) {
		while (y[ordy[j]] <= y[ordy[i]] - fy && j < i) {
			++j;
		}
		ry[ordy[i]] = j;
	}
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
	for (int i = 0; i < n; ++i) {
		auto mn = get(t[i], 0, n, 0, ry[i]);
		if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
	}
	for (int _ = 0; _ < 2 * k && !q.empty(); ++_) {
		int i = q.top().second;
		q.pop();
		auto mn = get(t[i], 0, n, 0, ry[i]);
		D.push_back({(long long)mn.first + x[i] + y[i], {min(i, ordy[mn.second]), max(i, ordy[mn.second])}});
		update(t[i], 0, n, mn.second, {INF, INF});
		mn = get(t[i], 0, n, 0, ry[i]);
		if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
	}
}

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
	}
	go(0, 0);
	for (int i = 0; i < n; ++i) {
		x[i] *= -1;
	}
	go(1, 0);
	sort(D.begin(), D.end());
	D.resize(unique(D.begin(), D.end()) - D.begin());
	D.resize(k);
	for (int i = 0; i < k; ++i) {
		cout << D[i].first << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 183200 KB Output is correct
2 Correct 803 ms 183260 KB Output is correct
3 Correct 349 ms 90064 KB Output is correct
4 Correct 296 ms 95700 KB Output is correct
5 Correct 583 ms 182072 KB Output is correct
6 Correct 11 ms 4052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4002 ms 951288 KB Output is correct
2 Correct 3308 ms 951256 KB Output is correct
3 Correct 485 ms 176080 KB Output is correct
4 Correct 2890 ms 950992 KB Output is correct
5 Correct 2840 ms 951300 KB Output is correct
6 Correct 2934 ms 951288 KB Output is correct
7 Correct 2979 ms 950668 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 345028 KB Output is correct
2 Correct 1714 ms 345096 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 935 ms 345068 KB Output is correct
5 Correct 1463 ms 344752 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 345028 KB Output is correct
2 Correct 1714 ms 345096 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 935 ms 345068 KB Output is correct
5 Correct 1463 ms 344752 KB Output is correct
6 Correct 1684 ms 345172 KB Output is correct
7 Correct 1695 ms 345156 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1682 ms 345124 KB Output is correct
11 Correct 924 ms 345220 KB Output is correct
12 Correct 1265 ms 344744 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 183200 KB Output is correct
2 Correct 803 ms 183260 KB Output is correct
3 Correct 349 ms 90064 KB Output is correct
4 Correct 296 ms 95700 KB Output is correct
5 Correct 583 ms 182072 KB Output is correct
6 Correct 11 ms 4052 KB Output is correct
7 Correct 4236 ms 700208 KB Output is correct
8 Correct 3994 ms 701940 KB Output is correct
9 Correct 284 ms 95588 KB Output is correct
10 Correct 3347 ms 701352 KB Output is correct
11 Correct 3163 ms 701068 KB Output is correct
12 Correct 2144 ms 701904 KB Output is correct
13 Correct 2683 ms 700116 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 183200 KB Output is correct
2 Correct 803 ms 183260 KB Output is correct
3 Correct 349 ms 90064 KB Output is correct
4 Correct 296 ms 95700 KB Output is correct
5 Correct 583 ms 182072 KB Output is correct
6 Correct 11 ms 4052 KB Output is correct
7 Correct 4002 ms 951288 KB Output is correct
8 Correct 3308 ms 951256 KB Output is correct
9 Correct 485 ms 176080 KB Output is correct
10 Correct 2890 ms 950992 KB Output is correct
11 Correct 2840 ms 951300 KB Output is correct
12 Correct 2934 ms 951288 KB Output is correct
13 Correct 2979 ms 950668 KB Output is correct
14 Correct 1712 ms 345028 KB Output is correct
15 Correct 1714 ms 345096 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 935 ms 345068 KB Output is correct
18 Correct 1463 ms 344752 KB Output is correct
19 Correct 1684 ms 345172 KB Output is correct
20 Correct 1695 ms 345156 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1682 ms 345124 KB Output is correct
24 Correct 924 ms 345220 KB Output is correct
25 Correct 1265 ms 344744 KB Output is correct
26 Correct 4236 ms 700208 KB Output is correct
27 Correct 3994 ms 701940 KB Output is correct
28 Correct 284 ms 95588 KB Output is correct
29 Correct 3347 ms 701352 KB Output is correct
30 Correct 3163 ms 701068 KB Output is correct
31 Correct 2144 ms 701904 KB Output is correct
32 Correct 2683 ms 700116 KB Output is correct
33 Correct 5445 ms 951988 KB Output is correct
34 Correct 5380 ms 957188 KB Output is correct
35 Correct 5130 ms 956348 KB Output is correct
36 Correct 3399 ms 957140 KB Output is correct
37 Correct 3537 ms 957188 KB Output is correct
38 Correct 3728 ms 955480 KB Output is correct