Submission #409058

#	Time	Username	Problem	Language	Result	Execution time	Memory
409058		ja_kingy	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	299 ms	19816 KiB

railroad

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

typedef long long ll;
typedef pair<int,int> pii;
int INF = 2e9;

int dsu[400000];

int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
bool merge(int a, int b) {
    a = f(a), b = f(b);
    if (a != b) {
        dsu[b] = a;
        return 1;
    }
    return 0;
}

int compress(vector<int> &vec, int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    ll ans = 0;
    iota(dsu, end(dsu), 0);
    vector<int> xs;
    t.push_back(1);
    s.push_back(INF);
    for (int i = 0; i < s.size(); ++i) {
        xs.push_back(s[i]);
        xs.push_back(t[i]);
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    vector<pii> evs;
    for (int i = 0; i < s.size(); ++i) {
        int a = compress(xs, s[i]), b = compress(xs, t[i]);
        evs.push_back({a, 1});
        evs.push_back({b, -1});
        merge(a,b);
    }
    sort(evs.begin(), evs.end());
    int d = 0, it = 0;
    vector<pii> es;
    for (int i = 0; i < xs.size() - 1; ++i) {
        es.push_back({xs[i+1]-xs[i],i});
        while (it < evs.size() && evs[it].first == i) {
            d += evs[it].second;
            it++;
        }
        if (d) merge(i, i+1);
        ans += (ll)max(0, d) * (xs[i+1]-xs[i]);
    }
    sort(es.begin(), es.end());
    for (pii e: es) {
        if (merge(e.second, e.second+1)) {
            ans += e.first;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~
railroad.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~
railroad.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < xs.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~
railroad.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (it < evs.size() && evs[it].first == i) {
      |                ~~~^~~~~~~~~~~~

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