Submission #205976

#	Time	Username	Problem	Language	Result	Execution time	Memory
205976		HungAnhGoldIBO2020	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	303 ms	25936 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
const long long N=4e5+2;
const long long inf=1e9+7;
vector<long long> coor;
long long head[N],cnt[N];
priority_queue<pair<long long,pair<long long,long long> > > lis;
long long findd(long long x){
	if(head[x]<0){
		return x;
	}
	long long y=findd(head[x]);
	head[x]=y;
	return y;
}
void unionn(long long x,long long y){
	x=findd(x),y=findd(y);
	head[x]+=head[y];
	head[y]=x;
}
bool samee(long long x,long long y){
	return findd(x)==findd(y);
}
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
	s.push_back(inf);
	t.push_back(1);
	long long n=s.size(),i,j,k,l,r,ans=0;
	for(i=0;i<n;i++){
		coor.push_back(s[i]);
		coor.push_back(t[i]);
	}
	sort(coor.begin(),coor.end());
	coor.erase(unique(coor.begin(),coor.end()),coor.end());
	for(i=0;i<(long long)coor.size();i++){
		head[i+1]=-1;
	}
	for(i=0;i<n;i++){
		l=lower_bound(coor.begin(),coor.end(),s[i])-coor.begin()+1;
		r=lower_bound(coor.begin(),coor.end(),t[i])-coor.begin()+1;
		cnt[l]++;
		cnt[r]--;
		if(!samee(l,r)){
			unionn(l,r);
		}
	}
	for(i=1;i<=(long long)coor.size();i++){
		cnt[i]+=cnt[i-1];
		if(i==(long long)coor.size()){
			assert(cnt[i]==0);
		}
		if(cnt[i]!=0){
			if(!samee(i,i+1)){
				unionn(i,i+1);
			}
			ans+=max(0ll,cnt[i])*(coor[i-1]-coor[i-2]);
		}
	}
	for(i=1;i<(long long)coor.size();i++){
		if(!samee(i,i+1)){
			lis.push({-(coor[i]-coor[i-1]),{i,i+1}});
		}
	}
	while(lis.size()){
		i=lis.top().first;
		j=lis.top().second.first;
		k=lis.top().second.second;
		lis.pop();
		if(samee(j,k)){
			continue;
		}
		unionn(j,k);	
		ans-=i;
	}
	return ans;
}

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