Submission #233092

#	Time	Username	Problem	Language	Result	Execution time	Memory
233092		islingr	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	243 ms	11868 KiB

railroad

#include <algorithm>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)

const int M = 1 << 19;
int nxt[M], rnk[M];

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;
	if (rnk[u] > rnk[v]) nxt[v] = u;
	else {
		nxt[u] = v;
		if (rnk[u] == rnk[v]) ++rnk[v];
	}
	return true;
}

const int inf = 2e9;
using ll = int64_t;
using vi = vector<int>;

ll plan_roller_coaster(vi s, vi t) {
	ll ans = 0;
	
	s.eb(inf); t.eb(1); int n = sz(s);

	vector<int> p = s; p.insert(end(p), all(t));
	sort(all(p)); p.erase(unique(all(p)), end(p));	
	int m = sz(p); rep(u, 0, m) nxt[u] = -1;

	vector<int> sum(m--);
	rep(i, 0, n) {
		int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
		unite(l, r);
		++sum[l]; --sum[r];
	}
	rep(i, 0, m) sum[i + 1] += sum[i];

	vector<int> e;
	rep(i, 0, m) {
		if (sum[i]) {
			unite(i + 1, i);
			if (sum[i] > 0) ans += 1ll * sum[i] * (p[i + 1] - p[i]);
		} else e.eb(i);
	}

	sort(all(e), [&p](int u, int v){ return p[u + 1] - p[u] < p[v + 1] - p[v]; });
	trav(u, e) if (unite(u, u + 1)) ans += p[u + 1] - p[u];

	return ans;
}

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