Submission #1047950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047950		Edu175	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	262 ms	53680 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto dkfjhg:v)cout<<dkfjhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=4e5+5,INF=1e15;
ll uf[MAXN];
ll uf_find(ll x){return uf[x]<0?x:uf[x]=uf_find(uf[x]);}
ll uf_join(ll x, ll y){
	x=uf_find(x),y=uf_find(y);
	if(x==y)return 0;
	if(uf[x]>uf[y])swap(x,y);
	uf[x]+=uf[y],uf[y]=x;
	return 1;
}
ll mst(vector<pair<ll,ii>>&ed){
	sort(ALL(ed));
	mset(uf,-1);
	ll res=0;
	for(auto [w,pa]:ed){
		if(uf_join(pa.fst,pa.snd))res+=w;
	}
	return res;
}

long long plan_roller_coaster(std::vector<int> A, std::vector<int> B) {
    vector<ll>a,b;
	for(auto i:A)a.pb(i);
	for(auto i:B)b.pb(i);
	a.pb(INF); b.pb(1);
	ll n=SZ(a);
	vector<ii>ev;
	fore(i,0,n){
		ev.pb({a[i],1});
		ev.pb({b[i],-1});
	}
	sort(ALL(ev));
	vector<pair<ll,ii>>ed;
	fore(i,0,n)ed.pb({0,{a[i],b[i]}});
	ll s=0,res=0;
	fore(i,0,SZ(ev)){
		s+=ev[i].snd;
		if(i<SZ(ev)-1&&ev[i].fst!=ev[i+1].fst){
			ll u=ev[i].fst,v=ev[i+1].fst;
			ll d=v-u;
			if(s>0)res+=d*s;
			if(s)ed.pb({0,{u,v}});
			ed.pb({d,{u,v}});
		}
	}
	
	//compress
	vector<ll>com;
	fore(i,0,n)com.pb(a[i]),com.pb(b[i]);
	sort(ALL(com));
	auto _com=com; com.clear();
	for(auto i:_com)if(!SZ(com)||i!=com.back())com.pb(i);
	auto getid=[&](ll v){
		return lower_bound(ALL(com),v)-com.begin();
	};
	
	for(auto &[w,pa]:ed){
		auto &[u,v]=pa;
		u=getid(u),v=getid(v);
	}
	res+=mst(ed);
	return res;
}

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