test/aizu-online-judge/2617.test.cpp

• View this file on GitHub
• Last update: 2021-11-09 11:45:13+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2617

Depends on

• Inversion (src/misc/inversion.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2617"

#include <iostream>
#include <numeric>

#include "src/misc/inversion.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<long long> p(n), l(n);
  for (auto &&x : p) {
    std::cin >> x;
  }
  for (auto &&x : l) {
    std::cin >> x;
  }

  std::partial_sum(p.begin(), p.end(), p.begin());

  auto ans = workspace::inversion(p.begin(), p.end());
  std::sort(p.begin(), p.end());

  for (auto i = n; --i;) p[i] -= p[i - 1];
  for (auto i = 0; i < n; ++i)
    if (p[i] < l[i]) {
      std::cout << "-1\n";
      return 0;
    }

  std::cout << ans << "\n";
}

#line 1 "test/aizu-online-judge/2617.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2617"

#include <iostream>
#include <numeric>

#line 2 "src/misc/inversion.hpp"

/**
 * @file inversion.hpp
 * @brief Inversion
 */

#include <algorithm>
#include <vector>

namespace workspace {

template <class _Iterator>
auto left_inversion(_Iterator __first, _Iterator __last) noexcept {
  std::vector<typename std::iterator_traits<_Iterator>::value_type> __v(__first,
                                                                        __last);
  std::sort(__v.begin(), __v.end(), std::greater<void>{});
  std::vector<size_t> __inv, __sum(__v.size() + 1);
  while (__first != __last) {
    auto& __c = __inv.emplace_back();
    size_t __e = std::distance(
        __v.begin(), std::lower_bound(__v.begin(), __v.end(), *__first++,
                                      std::greater<void>{}));
    for (auto __i = __e; __i; __i &= __i - 1) __c += __sum[__i];
    for (++__e; __e < __sum.size(); __e += __e & -__e) ++__sum[__e];
  }
  return __inv;
}

template <class _Iterator>
auto right_inversion(_Iterator __first, _Iterator __last) noexcept {
  std::vector<typename std::iterator_traits<_Iterator>::value_type> __v(__first,
                                                                        __last);
  std::sort(__v.begin(), __v.end());
  std::vector<size_t> __inv, __sum(__v.size() + 1);
  while (__first != __last) {
    auto& __c = __inv.emplace_back();
    size_t __e = std::distance(
        __v.begin(), std::lower_bound(__v.begin(), __v.end(), *--__last));
    for (auto __i = __e; __i; __i &= __i - 1) __c += __sum[__i];
    for (++__e; __e < __sum.size(); __e += __e & -__e) ++__sum[__e];
  }
  std::reverse(__inv.begin(), __inv.end());
  return __inv;
}

template <class _Iterator>
auto inversion(_Iterator __first, _Iterator __last) noexcept {
  uint_least64_t __res = 0;
  for (auto __x : left_inversion(__first, __last)) __res += __x;
  return __res;
}

}  // namespace workspace
#line 7 "test/aizu-online-judge/2617.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<long long> p(n), l(n);
  for (auto &&x : p) {
    std::cin >> x;
  }
  for (auto &&x : l) {
    std::cin >> x;
  }

  std::partial_sum(p.begin(), p.end(), p.begin());

  auto ans = workspace::inversion(p.begin(), p.end());
  std::sort(p.begin(), p.end());

  for (auto i = n; --i;) p[i] -= p[i - 1];
  for (auto i = 0; i < n; ++i)
    if (p[i] < l[i]) {
      std::cout << "-1\n";
      return 0;
    }

  std::cout << ans << "\n";
}

Back to top page