Submission #96873

#	Time	Username	Problem	Language	Result	Execution time	Memory
96873		youngyojun	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	294 ms	17044 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

const int MAXN = 200055;

int ud[MAXN*2], C[MAXN*2], O[MAXN*2];

vector<int> XV;
int A[MAXN], B[MAXN], AI[MAXN], BI[MAXN];

ll Ans;
int N, K;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

ll getAns() {
	XV.eb(0); XV.eb(INF);
	for(int i = 0; i < N; i++) {
		XV.eb(A[i]);
		XV.eb(B[i]);
	}
	sorv(XV); univ(XV); K = sz(XV);
	iota(ud, ud+K, 0);
	for(int i = 0; i < N; i++) {
		AI[i] = int(lower_bound(allv(XV), A[i]) - XV.begin());
		BI[i] = int(lower_bound(allv(XV), B[i]) - XV.begin());
		C[AI[i]]--; C[BI[i]]++;
		uf(AI[i], BI[i]);
	}
	C[0] = -1; C[1]++; uf(0, 1);
	for(int i = 2; i < K; i++) if(C[i-1]) {
		uf(i-1, i);
		if(C[i-1] < 0) Ans -= ll(C[i-1]) * (XV[i]-XV[i-1]);
		C[i] += C[i-1]; C[i-1] = 0;
	}
	iota(O, O+K, 0); sort(O+1, O+K, [&](int a, int b) {
		return XV[a]-XV[a-1] < XV[b]-XV[b-1];
	});
	for(int oi = 1, i; oi < K; oi++) {
		i = O[oi];
		if(uf(i-1) == uf(i)) continue;
		Ans += XV[i] - XV[i-1];
		uf(i-1, i);
	}
	return Ans;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	::N = sz(s);
	for(int i = 0; i < N; i++) {
		::A[i] = s[i];
		::B[i] = t[i];
	}
	return getAns();
}

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