Submission #369119

#	Time	Username	Problem	Language	Result	Execution time	Memory
369119		BartolM	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	408 ms	43208 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=4e5+50;

int n, maxi;
vector <int> ls[N];
vector <int> saz;
int desaz[N], val[N];
int P[N];
vector <pip> v;
#define DEBUG 0

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}
int mrg(int x, int y) {
    x=name(x); y=name(y);
    if (x==y) return 0;
    P[x]=y;
    return 1;
}

int sazmi(int x) {
    int ret=lower_bound(saz.begin(), saz.end(), x)-saz.begin();
    desaz[ret]=x;
    return ret;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    s.pb(INF); t.pb(1);
    n=s.size();
    ll sol=0;

    for (int i=0; i<n; ++i) saz.pb(s[i]), saz.pb(t[i]);
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    maxi=saz.size();

    for (int i=0; i<n; ++i) {
        s[i]=sazmi(s[i]);
        t[i]=sazmi(t[i]);
        ls[s[i]].pb(t[i]);

        val[s[i]]++, val[t[i]]--;
    }
    for (int i=0; i<maxi; ++i) {
        if (i) val[i]+=val[i-1];
//        printf("i: %d, desaz[i]: %d, val: %d\n", i, desaz[i], val[i]);
        if (val[i]<0) ls[i].pb(i+1);
        if (val[i]>0) {
            sol+=(ll)val[i]*(desaz[i+1]-desaz[i]);
            ls[i+1].pb(i);
        }
        P[i]=i;
    }
    #if DEBUG
        printf("stabilizacija: %lld\n", sol);
    #endif // DEBUG

    for (int i=0; i<maxi; ++i) {
        for (int sus:ls[i]) mrg(i, sus);
    }
    for (int i=0; i<maxi-1; ++i) {
        if (name(i)==name(i+1)) continue;
        v.pb(mp(desaz[i+1]-desaz[i], mp(name(i), name(i+1))));
    }
    sort(v.begin(), v.end());
    for (pip pp:v) sol+=(ll)pp.X*mrg(pp.Y.X, pp.Y.Y);
    return sol;

}

/*
4
1 7
4 3
5 8
6 6

*/

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