oj.uz

Submission #465764

# Submission time Handle Problem Language Result Execution time Memory
465764 2021-08-16T18:15:24 Z koioi.org-dennisstar Road Construction (JOI21_road_construction) C++17
33 / 100
 1988 ms 1598756 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<<26];
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));
}

void print(int i, int s, int e) {
	if (!i) return ;
	if (s==e) {
		printf("%d : %lld\n", s, nd[i].v.first);
		return ;
	}
	int m=(s+e)/2;
	print(nd[i].l, s, m);
	print(nd[i].r, m+1, e);
}

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[i].second==p[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 1578876 KB Output is correct
2 Correct 1022 ms 1578916 KB Output is correct
3 Correct 971 ms 1578976 KB Output is correct
4 Incorrect 955 ms 1578968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1462 ms 1594276 KB Output is correct
2 Correct 1459 ms 1597292 KB Output is correct
3 Correct 873 ms 1578764 KB Output is correct
4 Correct 1232 ms 1596968 KB Output is correct
5 Correct 1282 ms 1597148 KB Output is correct
6 Correct 1291 ms 1597260 KB Output is correct
7 Correct 1300 ms 1596612 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1925 ms 1593608 KB Output is correct
2 Correct 1859 ms 1598416 KB Output is correct
3 Correct 765 ms 1576176 KB Output is correct
4 Correct 1109 ms 1596236 KB Output is correct
5 Correct 1801 ms 1598756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1925 ms 1593608 KB Output is correct
2 Correct 1859 ms 1598416 KB Output is correct
3 Correct 765 ms 1576176 KB Output is correct
4 Correct 1109 ms 1596236 KB Output is correct
5 Correct 1801 ms 1598756 KB Output is correct
6 Correct 1988 ms 1598496 KB Output is correct
7 Correct 1954 ms 1598432 KB Output is correct
8 Correct 784 ms 1576144 KB Output is correct
9 Correct 802 ms 1576176 KB Output is correct
10 Correct 1897 ms 1598456 KB Output is correct
11 Correct 1110 ms 1596348 KB Output is correct
12 Correct 1798 ms 1598712 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 1578876 KB Output is correct
2 Correct 1022 ms 1578916 KB Output is correct
3 Correct 971 ms 1578976 KB Output is correct
4 Incorrect 955 ms 1578968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 1578876 KB Output is correct
2 Correct 1022 ms 1578916 KB Output is correct
3 Correct 971 ms 1578976 KB Output is correct
4 Incorrect 955 ms 1578968 KB Output isn't correct
5 Halted 0 ms 0 KB -