Submission #389042

#	Time	Username	Problem	Language	Result	Execution time	Memory
389042		Keshi	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	276 ms	27656 KiB

railroad

//In the name of God
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll dsu[maxn], sz[maxn], ps[maxn];

ll par(ll v){
	if(dsu[v] != v) dsu[v] = par(dsu[v]);
	return dsu[v];
}

bool Union(ll v, ll u){
	v = par(v);
	u = par(u);
	if(u == v) return 0;
	if(sz[v] < sz[u]) swap(v, u);
	sz[v] += sz[u];
	dsu[u] = v;
	return 1;
}

long long plan_roller_coaster(vector<int> s, vector<int> t){
	for(ll i = 0; i < maxn; i++){
		dsu[i] = i;
		sz[i] = 1;
	}
	s.pb(inf + 10);
	t.pb(0);
	ll n = Sz(s);
	vector<ll> vec;
	for(ll i = 0; i < n; i++){
		vec.pb(s[i]);
		vec.pb(t[i]);
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for(ll i = 0; i < n; i++){
		s[i] = lower_bound(all(vec), s[i]) - vec.begin();
		t[i] = lower_bound(all(vec), t[i]) - vec.begin();
		Union(s[i], t[i]);
		ps[s[i] + 1]++;
		ps[t[i] + 1]--;
	}
	vector<pll> e;
	ll ans = 0;
	for(ll i = 1; i < Sz(vec); i++){
		ps[i] += ps[i - 1];
		if(ps[i] > 0) ans += ps[i] * (vec[i] - vec[i - 1]);
		if(ps[i] == 0) e.pb(Mp(vec[i] - vec[i - 1], i));
		else Union(i - 1, i);
	}
	sort(all(e));
	for(pll i : e){
		if(Union(i.S, i.S - 1)){
			ans += i.F;
		}
	}
    return ans;
}

/*int main(){
    fast_io;



    return 0;
}*/

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