Submission #60158138

---

Source Code Expand

#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <iostream>
#include <vector>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

// ll pw(ll a, ll b) {
//   ll ans = 1;
//   while (b) {
//     while (!(b & 1))
//       b >>= 1, a = (a * a) % MOD;
//     ans = (ans * a) % MOD, --b;
//   }
//   return ans;
// }

struct Res {
  ll start;
  ll r;

  vector<pair<ll, ll>> df;
};

Res merge(Res a, Res b) {
  Res res;
  res.start = a.start + b.start;
  res.r = max(a.r, b.r);

  ll d = 0;
  int l = 0;
  int r = 0;
  while (l < a.df.size() || r < b.df.size()) {
    ll t = 1e9 + 100;
    if (l < a.df.size()) {
      t = min(t, a.df[l].first);
    }
    if (r < b.df.size()) {
      t = min(t, b.df[r].first);
    }
    ll add = 0;
    if (l < a.df.size() && a.df[l].first == t) {
      add += a.df[l].second;
      ++l;
    }
    if (r < b.df.size() && b.df[r].first == t) {
      add += b.df[r].second;
      ++r;
    }
    if (d + add > 0) {
      add = -d;
    }
    if (add != 0) {
      res.df.emplace_back(t, add);
    }
    d += add;
  }
  if (res.df.size() && res.df.back().first == res.r) {
    res.df.back().second += 1;
  } else {
    res.df.emplace_back(res.r, 1);
  }

  return res;
}

int n;
vector<pair<ll, ll>> vv;

Res solve(int l, int r) {
  if (l + 1 == r) {
    Res res;
    res.start = vv[l].first;
    res.r = vv[l].second;
    res.df.emplace_back(0, -1);
    res.df.emplace_back(vv[l].first, 1);
    res.df.emplace_back(vv[l].second, 1);
    return res;
  }
  int m = (l + r) / 2;
  return merge(solve(l, m), solve(m, r));
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  cin >> n;
  n = (1 << n);
  for (int i = 0; i < n; ++i) {
    ll l, r;
    cin >> l >> r;
    vv.emplace_back(l, r);
  }

  Res res = solve(0, n);
  ll cur = res.start;
  ll ans = cur;
  ll t = 0;
  ll d = 0;
  for (auto [x, y] : res.df) {
    cur += d * (x - t);
    d += y;
    t = x;
    ans = min(ans, cur);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘Res merge(Res, Res)’:
Main.cpp:41:12: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   41 |   while (l < a.df.size() || r < b.df.size()) {
      |          ~~^~~~~~~~~~~~~
Main.cpp:41:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   41 |   while (l < a.df.size() || r < b.df.size()) {
      |                             ~~^~~~~~~~~~~~~
Main.cpp:43:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   43 |     if (l < a.df.size()) {
      |         ~~^~~~~~~~~~~~~
Main.cpp:46:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   46 |     if (r < b.df.size()) {
      |         ~~^~~~~~~~~~~~~
Main.cpp:50:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   50 |     if (l < a.df.size() && a.df[l].first == t) {
      |         ~~^~~~~~~~~~~~~
Main.cpp:54:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   54 |     if (r < b.df.size() && b.df[r].first == t) {
      |         ~~^~~~~~~~~~~~~

Judge Result