#773847 (C++17) No.1115 二つの数列 / Two Sequences

提出ソース

結果

問題	No.1115 二つの数列 / Two Sequences
ユーザー	keijak
提出日時	2022-06-25 18:30:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	38 ms / 2,000 ms
コード長	4,981 bytes
コンパイル時間	2,323 ms
コンパイル使用メモリ	207,428 KB
実行使用メモリ	7,424 KB
最終ジャッジ日時	2024-11-14 18:47:59
合計ジャッジ時間	4,166 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	32 ms 6,912 KB
testcase_04	AC	36 ms 7,168 KB
testcase_05	AC	32 ms 6,912 KB
testcase_06	AC	30 ms 6,816 KB
testcase_07	AC	36 ms 7,168 KB
testcase_08	AC	3 ms 6,816 KB
testcase_09	AC	19 ms 6,820 KB
testcase_10	AC	31 ms 7,296 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	38 ms 7,296 KB
testcase_13	AC	37 ms 7,168 KB
testcase_14	AC	37 ms 7,424 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,820 KB
testcase_23	AC	4 ms 6,816 KB
testcase_24	AC	13 ms 6,820 KB
testcase_25	AC	28 ms 6,820 KB
testcase_26	AC	7 ms 6,820 KB
testcase_27	AC	17 ms 6,820 KB
testcase_28	AC	22 ms 6,820 KB
testcase_29	AC	29 ms 6,816 KB
testcase_30	AC	35 ms 7,168 KB
testcase_31	AC	10 ms 6,816 KB
testcase_32	AC	7 ms 6,820 KB
testcase_33	AC	29 ms 7,040 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	2 ms 6,816 KB
testcase_36	AC	2 ms 6,816 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	2 ms 6,820 KB
testcase_39	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #define NDEBUG
#include <bits/stdc++.h>

#define REP_(i, a_, b_, a, b, ...) for (int i = (a), END_##i = (b); i < END_##i; ++i)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(x) std::begin(x), std::end(x)
using Int = long long;
using Uint = unsigned long long;
using Real = long double;

template<typename T, typename U>
inline bool chmax(T &a, U b) { return a < b and ((a = b), true); }
template<typename T, typename U>
inline bool chmin(T &a, U b) { return a > b and ((a = b), true); }
template<typename T>
constexpr T kBigVal = std::numeric_limits<T>::max() / 2;
#if __cplusplus < 202002L
template<typename T>
inline int ssize(const T &a) { return (int) a.size(); }
#endif

struct CastInput {
  template<typename T>
  operator T() const {
    T x;
    std::cin >> x;
    assert(bool(std::cin));
    return x;
  }
  struct Sized {
    int n;
    template<typename T>
    operator T() const {
      T xs(n);
      for (auto &x: xs) {
        std::cin >> x;
        assert(bool(std::cin));
      }
      return xs;
    }
  };
  Sized operator()(int n) const { return {n}; }
} in;

template<typename Container>
std::ostream &out_seq(const Container &seq, const char *sep = " ",
                      const char *ends = "\n", std::ostream &os = std::cout) {
  const auto itl = std::begin(seq), itr = std::end(seq);
  for (auto it = itl; it != itr; ++it) {
    if (it != itl) os << sep;
    os << *it;
  }
  return os << ends;
}

template<typename T>
std::ostream &out_one(const T &x, char endc) {
  if constexpr (std::is_same<T, bool>::value) {
    return std::cout << (x ? "Yes" : "No") << endc;
  } else {
    return std::cout << x << endc;
  }
}
template<typename T>
std::ostream &out(const T &x) {
  return out_one(x, '\n');
}
template<typename T, typename... Ts>
std::ostream &out(const T &head, Ts... tail) {
  return out_one(head, ' '), out(tail...);
}

void init_(bool interactive = false) {
  std::ios::sync_with_stdio(false);
  if (not interactive) std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(18);
}

void exit_() {
#ifdef MY_DEBUG
  std::string _;
  assert((std::cin >> _).fail());
#endif
  std::cout.flush(), std::cerr.flush(), std::_Exit(0);
}

#ifdef MY_DEBUG
#include "debug_dump.hpp"
#include "backward.hpp"
backward::SignalHandling kSignalHandling;
#else
#define DUMP(...)
#define test_case(...)
#define cerr if(false)cerr
#endif

template<typename Monoid>
struct SegmentTree {
  using T = typename Monoid::T;

  int n_;                // number of valid leaves.
  int offset_;           // where leaves start
  std::vector<T> data_;  // data size: 2*offset_

  inline int size() const { return n_; }
  inline int offset() const { return offset_; }

  explicit SegmentTree(int n) : n_(n) {
    offset_ = 1;
    while (offset_ < n_) offset_ <<= 1;
    data_.assign(2 * offset_, Monoid::id());
  }

  explicit SegmentTree(const std::vector<T> &leaves) : n_(leaves.size()) {
    offset_ = 1;
    while (offset_ < n_) offset_ <<= 1;
    data_.assign(2 * offset_, Monoid::id());
    for (int i = 0; i < n_; ++i) {
      data_[offset_ + i] = leaves[i];
    }
    for (int i = offset_ - 1; i > 0; --i) {
      data_[i] = Monoid::op(data_[i * 2], data_[i * 2 + 1]);
    }
  }

  // Sets i-th value (0-indexed) to x.
  void set(int i, const T &x) {
    int k = offset_ + i;
    data_[k] = x;
    // Update its ancestors.
    while (k > 1) {
      k >>= 1;
      data_[k] = Monoid::op(data_[k * 2], data_[k * 2 + 1]);
    }
  }

  // Queries by [l,r) range (0-indexed, half-open interval).
  T fold(int l, int r) const {
    l = std::max(l, 0) + offset_;
    r = std::min(r, offset_) + offset_;
    T vleft = Monoid::id(), vright = Monoid::id();
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vleft = Monoid::op(vleft, data_[l++]);
      if (r & 1) vright = Monoid::op(data_[--r], vright);
    }
    return Monoid::op(vleft, vright);
  }

  T fold_all() const { return data_[1]; }

  // Returns i-th value (0-indexed).
  T operator[](int i) const { return data_[offset_ + i]; }

  std::vector<T> to_vec(int sz = -1) const {
    if (sz < 0 or sz > size()) sz = size();
    std::vector<T> res(sz);
    for (int i = 0; i < sz; ++i) res[i] = (*this)[i];
    return res;
  }
};

struct SumOp {
  using T = long long;
  static T op(const T &x, const T &y) {
    return x + y;
    // alt: saturating_add(x, y)
  }
  static constexpr T id() { return 0; }
  static T invert(const T &x) { return -x; }
};

using namespace std;

auto solve() {
  int n = in;
  vector<int> A = in(n), B = in(n);
  vector<int> ra(n), rb(n), C(n);
  REP(i, n) {
    --A[i];
    --B[i];
    ra[A[i]] = i;
    rb[B[i]] = i;
  }

  SegmentTree<SumOp> seg(n);
  Int inversion_count = 0;
  REP(i, n) {
    int j = ra[B[i]];
    inversion_count += seg.fold(j + 1, n);
    seg.set(j, seg[j] + 1);
  }
  out(inversion_count);
}

int main() {
  init_();
  const int T = 1;//in;
  REP(t, T) {
    test_case(t, T);
    (solve());
  }
  exit_();
}

yukicoder

結果

テストケース

ソースコード