oj.uz

Submission #465768

# Submission time Handle Problem Language Result Execution time Memory
465768 2021-08-16T18:22:22 Z koioi.org-dennisstar Road Construction (JOI21_road_construction) C++17
100 / 100
 2288 ms 812196 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

struct node {
	int l, r;
	pair<ll, int> v;
	node() : l(0), r(0), v(1e18, 0) {}
}nd[1<<25];
int nc;

void upd(int i, int i_, int s, int e, int t, ll v) {
	if (s==e) {
		nd[i].v={v, s};
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) {
		nd[i].l=++nc;
		nd[i].r=nd[i_].r;
		upd(nc, nd[i_].l, s, m, t, v);
	}else {
		nd[i].l=nd[i_].l;
		nd[i].r=++nc;
		upd(nc, nd[i_].r, m+1, e, t, v);
	}
	nd[i].v=min(nd[nd[i].l].v, nd[nd[i].r].v);
}

pair<ll, int> get(int i, int s, int e, int l, int r) {
	if (!i||r<l||e<l||r<s) return {1e18, 0};
	if (l<=s&&e<=r) return nd[i].v;
	int m=(s+e)/2;
	return min(get(nd[i].l, s, m, l, r), get(nd[i].r, m+1, e, l, r));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int n, k;
	cin>>n>>k;
	vector<pair<ll, ll>> p(n);
	for (auto &i:p) cin>>i.first>>i.second;

	sort(all(p));
	vector<int> ys(n), yi(n), b(n);
	for (int i=0; i<n; i++) ys[i]=i;
	sort(all(ys), [&](int x, int y) { return p[x].second<p[y].second; });
	for (int i=0; i<n; i++) {
		int j=i;
		for (; j<n&&p[ys[i]].second==p[ys[j]].second; j++) {
			b[ys[j]]=i;
			yi[ys[j]]=j;
		}
		i=j-1;
	}

	vector<int> ur(n), dr(n);
	priority_queue<pair<ll, int>> pq;
	for (int i=1; i<n; i++) {
		ur[i]=++nc;
		upd(nc, ur[i-1], 0, n-1, yi[i-1], -p[i-1].first+p[i-1].second);
		dr[i]=++nc;
		upd(nc, dr[i-1], 0, n-1, yi[i-1], -p[i-1].first-p[i-1].second);
	}

	auto up = [&](int i) {
		auto k=get(ur[i], 0, n-1, b[i], n-1);
		pq.emplace(-(p[i].first-p[i].second+k.first), i);
		int x=++nc;
		upd(x, ur[i], 0, n-1, k.second, 1e18);
		ur[i]=x;
	};

	auto down = [&](int i) {
		auto k=get(dr[i], 0, n-1, 0, b[i]-1);
		pq.emplace(-(p[i].first+p[i].second+k.first), i+n);
		int x=++nc;
		upd(x, dr[i], 0, n-1, k.second, 1e18);
		dr[i]=x;
	};

	for (int i=1; i<n; i++) up(i), down(i);

	while (k--) {
		auto [v, i]=pq.top();
		pq.pop();
		cout<<-v<<'\n';
		if (i<n) up(i);
		else down(i-n);
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 790832 KB Output is correct
2 Correct 612 ms 791076 KB Output is correct
3 Correct 590 ms 791004 KB Output is correct
4 Correct 567 ms 791112 KB Output is correct
5 Correct 627 ms 789744 KB Output is correct
6 Correct 375 ms 788368 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 806256 KB Output is correct
2 Correct 1095 ms 806436 KB Output is correct
3 Correct 471 ms 790828 KB Output is correct
4 Correct 866 ms 806144 KB Output is correct
5 Correct 904 ms 806284 KB Output is correct
6 Correct 895 ms 806280 KB Output is correct
7 Correct 911 ms 805500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1484 ms 805440 KB Output is correct
2 Correct 1506 ms 805380 KB Output is correct
3 Correct 370 ms 788252 KB Output is correct
4 Correct 732 ms 805628 KB Output is correct
5 Correct 1270 ms 805400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1484 ms 805440 KB Output is correct
2 Correct 1506 ms 805380 KB Output is correct
3 Correct 370 ms 788252 KB Output is correct
4 Correct 732 ms 805628 KB Output is correct
5 Correct 1270 ms 805400 KB Output is correct
6 Correct 1512 ms 805372 KB Output is correct
7 Correct 1472 ms 805408 KB Output is correct
8 Correct 372 ms 788152 KB Output is correct
9 Correct 371 ms 788244 KB Output is correct
10 Correct 1517 ms 805452 KB Output is correct
11 Correct 719 ms 805424 KB Output is correct
12 Correct 1326 ms 805368 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 790832 KB Output is correct
2 Correct 612 ms 791076 KB Output is correct
3 Correct 590 ms 791004 KB Output is correct
4 Correct 567 ms 791112 KB Output is correct
5 Correct 627 ms 789744 KB Output is correct
6 Correct 375 ms 788368 KB Output is correct
7 Correct 1493 ms 797476 KB Output is correct
8 Correct 1474 ms 797476 KB Output is correct
9 Correct 566 ms 790960 KB Output is correct
10 Correct 1087 ms 796660 KB Output is correct
11 Correct 1157 ms 796528 KB Output is correct
12 Correct 991 ms 797364 KB Output is correct
13 Correct 1078 ms 796316 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 790832 KB Output is correct
2 Correct 612 ms 791076 KB Output is correct
3 Correct 590 ms 791004 KB Output is correct
4 Correct 567 ms 791112 KB Output is correct
5 Correct 627 ms 789744 KB Output is correct
6 Correct 375 ms 788368 KB Output is correct
7 Correct 1076 ms 806256 KB Output is correct
8 Correct 1095 ms 806436 KB Output is correct
9 Correct 471 ms 790828 KB Output is correct
10 Correct 866 ms 806144 KB Output is correct
11 Correct 904 ms 806284 KB Output is correct
12 Correct 895 ms 806280 KB Output is correct
13 Correct 911 ms 805500 KB Output is correct
14 Correct 1484 ms 805440 KB Output is correct
15 Correct 1506 ms 805380 KB Output is correct
16 Correct 370 ms 788252 KB Output is correct
17 Correct 732 ms 805628 KB Output is correct
18 Correct 1270 ms 805400 KB Output is correct
19 Correct 1512 ms 805372 KB Output is correct
20 Correct 1472 ms 805408 KB Output is correct
21 Correct 372 ms 788152 KB Output is correct
22 Correct 371 ms 788244 KB Output is correct
23 Correct 1517 ms 805452 KB Output is correct
24 Correct 719 ms 805424 KB Output is correct
25 Correct 1326 ms 805368 KB Output is correct
26 Correct 1493 ms 797476 KB Output is correct
27 Correct 1474 ms 797476 KB Output is correct
28 Correct 566 ms 790960 KB Output is correct
29 Correct 1087 ms 796660 KB Output is correct
30 Correct 1157 ms 796528 KB Output is correct
31 Correct 991 ms 797364 KB Output is correct
32 Correct 1078 ms 796316 KB Output is correct
33 Correct 2281 ms 812076 KB Output is correct
34 Correct 2288 ms 812144 KB Output is correct
35 Correct 1835 ms 811456 KB Output is correct
36 Correct 1609 ms 812132 KB Output is correct
37 Correct 1642 ms 812196 KB Output is correct
38 Correct 1728 ms 810912 KB Output is correct