Submission #530752

#	Time	Username	Problem	Language	Result	Execution time	Memory
530752		Cyanmond	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	215 ms	17464 KiB

railroad

#include <bits/stdc++.h>

using i64 = long long;
template <typename T> using Vec = std::vector<T>;

constexpr int inf = 1100000000;
constexpr i64 inf64 = 2000000000000000000;

template <typename T> bool setmin(T &a, const T v) {
    if (a > v) {
        a = v;
        return true;
    }
    return false;
}

long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    const int N = (int)S.size();
    std::vector<int> order(N);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](const int a, const int b) {
        if (S[a] != S[b])
            return S[a] < S[b];
        else
            return T[a] < T[b];
    });

    auto renum = [&](std::vector<int> &vec) {
        std::vector<int> new_vec(N);
        for (int i = 0; i < N; ++i) {
            new_vec[i] = vec[order[i]];
        }
        vec = std::move(new_vec);
    };
    renum(S);
    renum(T);

    std::set<std::pair<int, int>> set;
    for (int i = 1; i < N; ++i) set.insert({S[i], T[i]});
    i64 answer = 0;
    int now_s = S[0], now_t = T[0];
    while (not set.empty()) {
        auto itr = set.lower_bound({now_t, -inf});
        if (itr != set.end()) {
            now_s = itr->first;
            now_t = itr->second;
            set.erase(itr);
        } else {
            --itr;
            answer += now_t - (itr->first);
            now_s = itr->first;
            now_t = itr->second;
            set.erase(itr);
        }
    }

    // subtask 3
    return answer;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:41:9: warning: variable 'now_s' set but not used [-Wunused-but-set-variable]
   41 |     int now_s = S[0], now_t = T[0];
      |         ^~~~~

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