Submission #1012350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012350		hotboy2703	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	142 ms	24356 KiB

railroad

#include "railroad.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

const ll MAXN = 2e5+10;
ll dsu[MAXN*2];
ll f(ll x){
    if (dsu[x] < 0)return x;
    return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
//    cout<<x<<' '<<y<<'\n';
    x = f(x),y = f(y);
//    cout<<x<<' '<<y<<'\n';
    if (x != y){
        if (dsu[x] > dsu[y])swap(x,y);
        dsu[x] += dsu[y];
        dsu[y] = x;
        return 1;
    }
    return 0;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    memset(dsu,-1,sizeof dsu);
    s.push_back(1e9);
    t.push_back(1);
    int n = (int) s.size();
    vector <ll> val;
    for (ll i = 0;i < n;i ++){
        val.push_back(s[i]);
        val.push_back(t[i]);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    vector <ll> cnt(sz(val));
    for (ll i = 0;i < n;i ++){
        ll l = lower_bound(val.begin(),val.end(),s[i])-val.begin();
        ll r = lower_bound(val.begin(),val.end(),t[i])-val.begin();
        join(l,r);
        cnt[l]++,cnt[r]--;
    }
    for (ll i = 1;i < sz(val);i ++){
        cnt[i] += cnt[i-1];
    }
    ll res = 0;
    vector <pll> edges;
    for (ll i = 0;i + 1 < sz(val);i ++){
        if (cnt[i] != 0)join(i,i+1);
        else {
            edges.push_back(MP(val[i+1]-val[i],i));
        }
        res += max(0LL,cnt[i]) * (val[i+1]-val[i]);
    }
//    cout<<res<<'\n';
    sort(edges.begin(),edges.end());
    for (auto x:edges){
        if (join(x.se,x.se+1)){
            res += x.fi;
        }
    }
    return res;
}

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