Submission #255575

#	Time	Username	Problem	Language	Result	Execution time	Memory
255575		Mercenary	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	218 ms	15080 KiB

railroad

//#include "railroad.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 4e5 + 5;

int lab[maxn];
int sum[maxn];

vector<int> val;
int n;
int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
bool Merge(int u , int v){
    u = FindLab(u);v = FindLab(v);
    if(u == v)return 0;
    if(lab[u] > lab[v])swap(u , v);
    lab[u] += lab[v];
    lab[v] = u;
    return 1;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
    memset(lab,-1,sizeof lab);
    ll res = 0;
    n = s.size();
    for(int i = 0 ; i < n ; ++i){
        val.pb(s[i]);val.pb(t[i]);
    }
    sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
    for(int i = 0 ; i < n ; ++i){
        s[i] = lower_bound(val.begin(),val.end(),s[i]) - val.begin();
        t[i] = lower_bound(val.begin(),val.end(),t[i]) - val.begin();
        Merge(s[i] , t[i]);
        sum[s[i]]++;sum[t[i]]--;
    }
    int cur = 1;
    vector<pair<int,int>> edges;
    for(int i = (int)val.size() - 1 ; i > 0 ; --i){
        cur += sum[i];
        if(cur < 0){
            res -= 1ll * cur * (val[i] - val[i - 1]);
            Merge(i,i-1);
        }else if(cur > 0)Merge(i,i-1);
        else if(cur == 0)edges.pb(mp(val[i] - val[i - 1] , i));
    }
    sort(edges.begin(),edges.end());
    for(auto & c : edges){
        if(Merge(c.second,c.second-1))res += c.first;
    }
    return res;
}


//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    if(fopen(taskname".INP","r")){
//		freopen(taskname".INP", "r",stdin);
//		freopen(taskname".OUT", "w",stdout);
//    }
//
//}

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