Submission #258815

#	Time	Username	Problem	Language	Result	Execution time	Memory
258815		EntityIT	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	98 ms	6888 KiB

bridge

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

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

template<class T>
struct BIT {
  vec<T, 1> a;
  bool reversed;
  BIT(int n, bool t_reversed = false)
      : a(n),
        reversed(t_reversed) {}

  template<class U>
  void Add(int i, U value) {
    for (i = reversed ? SZ(a) - 1 - i : i; i < SZ(a); i |= i + 1) {
      a[i] += value;
    }
  }
  T Get(int i) const {
    T ret{};
    for (i = reversed ? SZ(a) - 1 - i : i; ~i; i = (i & (i + 1)) - 1) {
      ret += a[i];
    }
    return ret;
  }

  template<class U>
  void AddPosition(int i, U value) {
    Add(i, value);
  }
  T GetRange(int l, int r) const { return Get(r) - Get(l - 1); }

  template<class U>
  void AddRange(int l, int r, U value) {
    Add(l, value);
    Add(r + 1, -value);
  }
  T GetPosition(int i) const {
    return Get(i);
  }

  int LowerBound(T value) const {
    return UpperBound(value - 1);
  }
  int UpperBound(T value) const {
    int ret = 0;
    for (int i = __lg(SZ(a)); ~i; --i) {
      ret ^= 1 << i;
      if (ret <= SZ(a) && value >= a[ret - 1]) {
        value -= a[ret - 1];
      } else {
        ret ^= 1 << i;
      }
    }
    return ret;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_citizens, n_bridges; cin >> n_bridges >> n_citizens;

  int64_t answer = 0;
  vec<pair<int, int>, 1> intervals;
  vec<int, 1> xs;
  while (n_citizens--) {
    char source_zone, target_zone; int source_x, target_x; cin >> source_zone >> source_x >> target_zone >> target_x;
    if (source_zone != target_zone) {
      ++answer;
      intervals.emplace_back(min(source_x, target_x), max(source_x, target_x));
      xs.emplace_back(intervals.back().first);
      xs.emplace_back(intervals.back().second);
    } else {
      answer += abs(source_x - target_x);
    }
  }
  sort(ALL(intervals), [&](const auto& i, const auto& j) {
    return i.first + i.second < j.first + j.second;
  });
  sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());

  BIT<int> bit_left_amount(SZ(xs)), bit_right_amount(SZ(xs));
  BIT<int64_t> bit_left_sum(SZ(xs)), bit_right_sum(SZ(xs));
  for (auto& interval : intervals) {
    int index_x = static_cast<int>(lower_bound(ALL(xs), interval.first) - xs.begin());
    bit_right_amount.Add(index_x, 1);
    bit_right_sum.Add(index_x, interval.first);

    index_x = static_cast<int>(lower_bound(ALL(xs), interval.second) - xs.begin());
    bit_right_amount.Add(index_x, 1);
    bit_right_sum.Add(index_x, interval.second);
  }

  int64_t result = numeric_limits<int64_t>::max();
  auto Solve = [&]() {
    int64_t ret = 0;

    int amount = bit_left_amount.Get(SZ(xs) - 1),
        index_x = bit_left_amount.LowerBound(amount >> 1);
    if (amount) {
      ret += bit_left_sum.Get(SZ(xs) - 1) - (bit_left_sum.Get(index_x) << 1) +  static_cast<int64_t>(xs[index_x]) * ((bit_left_amount.Get(index_x) << 1) - amount);
    }

    amount = bit_right_amount.Get(SZ(xs) - 1);
    index_x = bit_right_amount.LowerBound(amount >> 1);
    if (amount) {
      ret += bit_right_sum.Get(SZ(xs) - 1) - (bit_right_sum.Get(index_x) << 1) +  static_cast<int64_t>(xs[index_x]) * ((bit_right_amount.Get(index_x) << 1) - amount);
    }

    Minimize(result, ret);
  };

  Solve();
  assert(n_bridges == 1);
  // if (n_bridges == 2) {
  //   for (auto& interval : intervals) {
  //     int index_x = static_cast<int>(lower_bound(ALL(xs), interval.first) - xs.begin());
  //     bit_left_amount.Add(index_x, 1);
  //     bit_left_sum.Add(index_x, interval.first);
  //     bit_right_amount.Add(index_x, -1);
  //     bit_right_sum.Add(index_x, -interval.first);

  //     index_x = static_cast<int>(lower_bound(ALL(xs), interval.second) - xs.begin());
  //     bit_left_amount.Add(index_x, 1);
  //     bit_left_sum.Add(index_x, interval.second);
  //     bit_right_amount.Add(index_x, -1);
  //     bit_right_sum.Add(index_x, -interval.second);

  //     Solve();
  //   }
  // }

  cout << answer + result << '\n';

  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37