Submission #45217

#	Time	Username	Problem	Language	Result	Execution time	Memory
45217		reality	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	340 ms	159080 KiB

railroad

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#include "railroad.h"
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int oo = 1e9 + 5;
const int N = (int)(1e6) + 5;
int sum[N];
int f[N];
int get(int k)
{
    return k == f[k] ? k : f[k] = get(f[k]);
}
ll plan_roller_coaster(vi l,vi r)
{
    l.pb(oo);
    r.pb(1);
    int n = l.size();
    vi ss;
    for (int i = 0;i < n;++i)
        ss.pb(l[i]),ss.pb(r[i]);
    sort(all(ss));
    ss.resize(unique(all(ss)) - ss.begin());
    const int sz = ss.size();
    for (int i = 1;i <= sz;++i)
        f[i] = i;
    for (int i = 0;i < n;++i)
    {
        int l1 = lower_bound(all(ss),l[i]) - ss.begin() + 1;
        int r1 = lower_bound(all(ss),r[i]) - ss.begin() + 1;
        sum[l1] += 1;
        sum[r1] -= 1;
        f[get(l1)] = get(r1);
    }
    ll ans = 0;
    for (int i = 1;i <= sz;++i)
        sum[i] += sum[i - 1];
    for (int i = 1;i <= sz;++i)
        if (sum[i])
            ans += 1ll * max(0,sum[i]) * (ss[i] - ss[i - 1]),f[get(i)] = get(i + 1);
    vi p;
    for (int i = 0;i + 1 < sz;++i)
        p.pb(i);
    sort(all(p),[&](int x,int y)
         {
            return ss[x + 1] - ss[x] < ss[y + 1] - ss[y];
         });
    for (auto index : p)
        if (get(index + 1) != get(index + 2))
            ans += ss[index + 1] - ss[index],f[get(index + 1)] = get(index + 2);
    return ans;
}

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