Submission #600277

#	Time	Username	Problem	Language	Result	Execution time	Memory
600277		valerikk	Road Construction (JOI21_road_construction)	C++17	100 / 100	3309 ms	648352 KiB

road_construction

#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; _ < 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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35