oj.uz

Submission #258825

# Submission time Handle Problem Language Result Execution time Memory
258825 2020-08-06T15:11:28 Z EntityIT Palembang Bridges (APIO15_bridge) C++14
100 / 100
 174 ms 9360 KB 
#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{};
    Minimize(i, SZ(a) - 1);
    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();
  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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 412 KB Output is correct
8 Correct 1 ms 408 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 27 ms 2532 KB Output is correct
13 Correct 102 ms 7268 KB Output is correct
14 Correct 60 ms 2548 KB Output is correct
15 Correct 54 ms 4716 KB Output is correct
16 Correct 33 ms 2548 KB Output is correct
17 Correct 62 ms 7268 KB Output is correct
18 Correct 60 ms 7268 KB Output is correct
19 Correct 79 ms 6972 KB Output is correct
20 Correct 39 ms 2540 KB Output is correct
21 Correct 71 ms 7264 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 31 ms 2932 KB Output is correct
26 Correct 53 ms 3060 KB Output is correct
27 Correct 167 ms 8160 KB Output is correct
28 Correct 173 ms 9184 KB Output is correct
29 Correct 174 ms 9360 KB Output is correct
30 Correct 83 ms 5100 KB Output is correct
31 Correct 39 ms 3812 KB Output is correct
32 Correct 113 ms 9184 KB Output is correct
33 Correct 109 ms 8968 KB Output is correct
34 Correct 127 ms 8932 KB Output is correct
35 Correct 42 ms 4076 KB Output is correct
36 Correct 122 ms 9060 KB Output is correct
37 Correct 30 ms 2932 KB Output is correct