Submission #1080667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080667		asdasdqwer	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	122 ms	15188 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct Segtree {
    vector<array<ll,2>> seg;int n;

    Segtree(int sz) {
        n = sz;
        seg.assign(2*n, {0, 0});
    }

    array<ll, 2> combine(array<ll, 2> a, array<ll, 2> b) {
        if (a[0] < b[0]) return a;
        return b;
    }

    void st(int i,  int v) {
        i+=n;
        seg[i] = {v, i-n};

        for (;i>1;i>>=1) {
            seg[i>>1] = min(seg[i], seg[i^1]);
        }
    }

    array<ll,2> get(int l, int r) {
        array<ll,2> res = {(int)1e18, 0};
        for (l += n, r+=n; l<r;l>>=1,r>>=1) {
            if ((l & 1)) res = combine(res, seg[l++]);
            if ((r&1)) res = combine(res, seg[--r]);
        }
        return res;
    }
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    if (n <= 16) {
        vector<vector<ll>> dp((1<<n), vector<ll>(n, 1e18));

        for (int i=1;i<(1<<n);i++) {
            if (__builtin_popcount(i) == 1) {
                for (int j=0;j<n;j++) dp[i][j]=0;
                continue;
            }

            for (int j=0;j<n;j++) {
                if ((i & (1<<j)) == 0) continue;
                for (int k=0;k<n;k++) {
                    if (k == j || (i & (1<<k)) == 0) continue;
                    ll val = dp[i ^ (1<<j)][k] + max(0, t[k]-s[j]);
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }

        ll mn = 1e18;
        for (int i=0;i<n;i++) {
            mn = min(mn, dp.back()[i]);
        }

        return mn;
    }

    // check if the answer can be zero
    vector<array<int,2>> v(n);
    for (int i=0;i<n;i++) {
        v[i]={s[i], t[i]};
    }

    sort(v.begin(), v.end());

    for (int i=0;i<n;i++) {
        s[i]=v[i][0];
        t[i]=v[i][1];
    }

    Segtree sg(n);
    for (int i=0;i<n;i++) {
        sg.st(i, t[i]);
    }

    int velo = 1;
    for (int i=0;i<n;i++) {
        auto it = lower_bound(s.begin(), s.end(), velo);
        if (it == s.end()) return 1;
        int idx = distance(s.begin(), it);
        auto res = sg.get(idx, n);
        if (res[0] == (int)1e18) return 1;
        velo = res[0];
        sg.st(res[1], (int)1e18);
    }

    return 0;
}

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