#576457 (C++17) No.1282 Display Elements

• 問題: No.1282 Display Elements
• ユーザー: KoD
• 提出日時: 2020-11-06 21:48:08
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 109 ms / 2,000 ms
• コード長: 6,167 bytes
• コンパイル時間: 794 ms
• コンパイル使用メモリ: 86,612 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2024-07-22 12:38:52
• 合計ジャッジ時間: 2,389 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	100 ms; 6,272 KB
testcase_16	AC	40 ms; 5,376 KB
testcase_17	AC	84 ms; 5,760 KB
testcase_18	AC	50 ms; 5,376 KB
testcase_19	AC	78 ms; 5,376 KB
testcase_20	AC	75 ms; 5,376 KB
testcase_21	AC	109 ms; 6,400 KB
testcase_22	AC	83 ms; 5,376 KB
testcase_23	AC	107 ms; 6,528 KB

ソースコード

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp"

template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}

template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/container/fenwick_tree.cpp"

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/bit_operation.cpp"

#include <cstddef>
#include <cstdint>

constexpr size_t bit_ppc(const uint64_t x) { return __builtin_popcountll(x); }
constexpr size_t bit_ctzr(const uint64_t x) { return x == 0 ? 64 : __builtin_ctzll(x); }
constexpr size_t bit_ctzl(const uint64_t x) { return x == 0 ? 64 : __builtin_clzll(x); }
constexpr size_t bit_width(const uint64_t x) { return 64 - bit_ctzl(x); }
constexpr uint64_t bit_msb(const uint64_t x) { return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1); }
constexpr uint64_t bit_lsb(const uint64_t x) { return x & (-x); }
constexpr uint64_t bit_cover(const uint64_t x) { return x == 0 ? 0 : bit_msb(2 * x - 1); }

constexpr uint64_t bit_rev(uint64_t x) {
  x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
  x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
  x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
  x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
  x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
  x = (x >> 32) | (x << 32);
  return x;
}

/**
 * @title Bit Operations
 */
#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/container/fenwick_tree.cpp"

#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/container/fenwick_tree.cpp"
#include <type_traits>

template <class T>
class fenwick_tree {
public:
  using value_type = T;
  using size_type = size_t;

private:
  std::vector<value_type> M_tree;

public:
  fenwick_tree() = default;
  explicit fenwick_tree(size_type size) { initialize(size); }

  void initialize(size_type size) {
    M_tree.assign(size + 1, value_type { });
  }

  void add(size_type index, const value_type& x) {
    assert(index < size());
    ++index;
    while (index <= size()) {
      M_tree[index] += x;
      index += bit_lsb(index);
    }
  }

  template <size_type Indexed = 1>
  value_type get(size_type index) const {
    assert(index < size());
    index += Indexed;
    value_type res{ };
    while (index > 0) {
      res += M_tree[index];
      index -= bit_lsb(index);
    }
    return res;
  }
  value_type fold(size_type first, size_type last) const {
    assert(first <= last);
    assert(last <= size());
    value_type res{};
    while (first < last) {
      res += M_tree[last];
      last -= bit_lsb(last);
    }
    while (last < first) {
      res -= M_tree[first];
      first -= bit_lsb(first);
    }
    return res;
  }

  template <class Func>
  size_type satisfies(const size_type left, Func &&func) const {
    assert(left <= size());
    if (func(value_type { })) return left;
    value_type val = -get<0>(left);
    size_type res = 0;
    for (size_type cur = bit_cover(size() + 1) >> 1; cur > 0; cur >>= 1) {
      if ((res + cur <= left) || (res + cur <= size() && !func(val + M_tree[res + cur]))) {
        val += M_tree[res + cur];
        res += cur;
      }
    }
    return res + 1;
  }

  void clear() {
    M_tree.clear();
    M_tree.shrink_to_fit();
  }
  size_type size() const {
    return M_tree.size() - 1;
  }
};

/**
 * @title Fenwick Tree
 */
#line 17 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

int main() {
  usize N;
  std::cin >> N;
  std::vector<u32> A(N), B(N);
  for (auto &x: A) {
    std::cin >> x;
  }
  for (auto &x: B) {
    std::cin >> x;
  }
  std::sort(A.begin(), A.end());
  std::vector<u32> cmp;
  cmp.reserve(2 * N);
  for (const auto x: A) {
    cmp.push_back(x);
  }
  for (const auto x: B) {
    cmp.push_back(x);
  }
  std::sort(cmp.begin(), cmp.end());
  cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
  for (auto &x: A) {
    x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
  }
  for (auto &x: B) {
    x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
  }
  const auto Size = cmp.size();
  fenwick_tree<usize> fen(Size);
  u64 ans = 0;
  for (auto i: range(0, N)) {
    fen.add(B[i], 1);
    ans += fen.fold(0, A[i]);
  }
  std::cout << ans << '\n';
  return 0;
}