Submission #662910

#	Time	Username	Problem	Language	Result	Execution time	Memory
662910		Trisanu_Das	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	171 ms	15116 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define eb(x...) emplace_back(x)
 
const int inf = 2e9;
using ll = int64_t;
using vi = vector<int>;
 
vi nxt;
int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return false;
	nxt[v] = u; return true;
}
 
ll plan_roller_coaster(vi s, vi t) {
	s.eb(inf); t.eb(1); int n = s.size();
	vi p = s; p.insert(end(p), all(t));
	sort(all(p)); p.erase(unique(all(p)), end(p));	
	int m = p.size(); nxt.resize(m, -1);
 
	vi b(m--);
	for(int i = 0; i < n; i++) {
		int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
		unite(l, r); ++b[l]; --b[r];
	}
	for(int i = 0; i < m; i++) b[i + 1] += b[i];
 
	vector<pair<int, int>> e; ll ans = 0;
	for(int i = 0; i < m; i++) {
		ll d = p[i + 1] - p[i];
		if (b[i]) {
			unite(i, i + 1);
			if (b[i] > 0) ans += b[i] * d;
		} else e.eb(d, i);
	}
	sort(all(e));
	for (auto u : e) if (unite(u.second, u.second + 1)) ans += u.first;
 
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36