Submission #1070357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070357		amirhoseinfar1385	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	150 ms	38688 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=600000+10;
vector<long long>allind;
long long n,vorod[maxn],khoroj[maxn],inf=1e9+5;

struct dsu{
    long long par[maxn];
    dsu(){
        for(long long i=0;i<maxn;i++){
            par[i]=i;
        }
    }
    long long root(long long u){
        if(u==par[u]){
            return u;
        }
        return par[u]=root(par[u]);
    }
    long long con(long long u,long long v){
        u=root(u);v=root(v);
        if(u==v){
            return 0;
        }
        par[u]=v;
        return 1;
    }
}ds,ds2;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(inf);
    t.push_back(1);
    n=(long long)s.size();
    for(long long i=0;i<n;i++){
        allind.push_back(s[i]);
        allind.push_back(t[i]);
    }
    sort(allind.begin(),allind.end());
    allind.resize(unique(allind.begin(),allind.end())-allind.begin());
    for(long long i=0;i<n;i++){
        long long pp=lower_bound(allind.begin(),allind.end(),s[i])-allind.begin();
        khoroj[pp]++;
        long long p=lower_bound(allind.begin(),allind.end(),t[i])-allind.begin();
        vorod[p]++;
        ds.con(p,pp);
    }
    long long mainres=0,vo=0,ko=0;
    for(long long i=0;i<(long long)allind.size();i++){
        ko+=khoroj[i];
        vo+=vorod[i];
        if(ko>vo){
            mainres+=(ko-vo)*(allind[i+1]-allind[i]);
        }
        if(ko!=vo){
            ds.con(i,i+1);
        }
    }
    vector<pair<long long ,pair<long long ,long long>>>allv;
    for(long long i=0;i<(long long)allind.size()-1;i++){
        if(ds.root(i)!=ds.root(i+1)){
            allv.push_back(make_pair(allind[i+1]-allind[i],make_pair(ds.root(i),ds.root(i+1))));
        }
    }
    sort(allv.begin(),allv.end());
    for(long long i=0;i<(long long)allv.size();i++){
        if(ds2.con(allv[i].second.first,allv[i].second.second)){
            mainres+=allv[i].first;
        }
    }
    return mainres;
}

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