Submission #136409

#	Time	Username	Problem	Language	Result	Execution time	Memory
136409		MAMBA	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	298 ms	17624 KiB

railroad

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

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;

const int N = 2e6 + 10;

int par[N];

int getPar(int v) { return v == par[v] ? v : par[v] = getPar(par[v]); }

bool merge(int a, int b) {
  if ((a = getPar(a)) == (b = getPar(b))) return false;
  return par[a] = b, true;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  s.pb(1e9);
  t.pb(1);

  vi me(all(s));
  for (auto e : t) me.pb(e);
  sort(all(me));
  me.resize(unique(all(me)) - me.begin());

  for (auto &e : s) e = lower_bound(all(me), e) - me.begin();
  for (auto &e : t) e = lower_bound(all(me), e) - me.begin();

  int n = s.size();
  vi cnt(me.size());

  iota(par, par + me.size(), 0);

  rep(i, 0, n) {
    merge(s[i], t[i]);
    cnt[s[i]]++;
    cnt[t[i]]--;
  }

  ll res = 0;

  int local = 0;
  rep(i, 0, me.size() - 1) {
    local += cnt[i];
    if (local < 0) {
      merge(i, i + 1);
    }
    if (local > 0) {
      res += 1ll * local * (me[i + 1] - me[i]);
      merge(i, i + 1);
    }
  }

  vi ind(me.size() - 1);
  iota(all(ind), 0);

  sort(all(ind),
       [&](int a, int b) { return me[a + 1] - me[a] < me[b + 1] - me[b]; });

  for (auto e : ind)
    if (merge(e, e + 1)) res += me[e + 1] - me[e];

  return res;
}

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