結果

問題 No.1282 Display Elements
ユーザー HaarHaar
提出日時 2020-11-06 21:45:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 78 ms / 2,000 ms
コード長 5,482 bytes
コンパイル時間 2,171 ms
コンパイル使用メモリ 210,176 KB
実行使用メモリ 7,660 KB
最終ジャッジ日時 2023-09-29 18:32:40
合計ジャッジ時間 3,666 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 71 ms
7,408 KB
testcase_16 AC 26 ms
4,896 KB
testcase_17 AC 57 ms
6,600 KB
testcase_18 AC 33 ms
5,144 KB
testcase_19 AC 33 ms
7,604 KB
testcase_20 AC 31 ms
7,608 KB
testcase_21 AC 78 ms
7,660 KB
testcase_22 AC 46 ms
7,656 KB
testcase_23 AC 78 ms
7,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}

std::string YesNo(bool value){return value ? "Yes" : "No";}
std::string YESNO(bool value){return value ? "YES" : "NO";}
std::string yesno(bool value){return value ? "yes" : "no";}

template <typename T>
void putl(const T &value){
  std::cout << value << "\n";
}

template <typename Head, typename ... Tail>
void putl(const Head head, const Tail &... tail){
  std::cout << head << " ";
  putl(tail ...);
}

#line 4 "/home/haar/Downloads/kyopro-lib/Mylib/Utils/compressor.cpp"

namespace haar_lib {
  template <typename T>
  class compressor {
    std::vector<T> data_;
    template <typename> friend class compressor_builder;

  public:
    int get_index(const T &val) const {
      return std::lower_bound(data_.begin(), data_.end(), val) - data_.begin();
    }

    auto& compress(std::vector<T> &vals) const {
      for(auto &x : vals) x = get_index(x);
      return *this;
    }

    auto& compress(T &val) const {
      val = get_index(val);
      return *this;
    }

    template <typename U, typename ... Args>
    auto& compress(U &val, Args &... args) const {
      compress(val);
      return compress(args ...);
    }

    auto& decompress(std::vector<T> &vals) const {
      for(auto &x : vals) x = data_[x];
      return *this;
    }

    auto& decompress(T &val) const {
      val = data_[val];
      return *this;
    }

    template <typename U, typename ... Args>
    auto& decompress(U &val, Args &... args) const {
      decompress(val);
      return decompress(args ...);
    }

    int size() const {return data_.size();}
    T operator[](int index) const {return data_[index];}
  };

  template <typename T>
  class compressor_builder {
    std::vector<T> data_;

  public:
    auto& add(const T &val){
      data_.push_back(val);
      return *this;
    }

    auto& add(const std::vector<T> &vals){
      data_.insert(data_.end(), vals.begin(), vals.end());
      return *this;
    }

    template <typename U, typename ... Args>
    auto& add(const U &val, const Args &... args){
      add(val);
      return add(args ...);
    }

    auto build() const {
      compressor<T> ret;
      ret.data_ = data_;
      std::sort(ret.data_.begin(), ret.data_.end());
      ret.data_.erase(std::unique(ret.data_.begin(), ret.data_.end()), ret.data_.end());
      return ret;
    }
  };
}
#line 4 "/home/haar/Downloads/kyopro-lib/Mylib/DataStructure/FenwickTree/fenwick_tree_add.cpp"

namespace haar_lib {
  template <typename T>
  class fenwick_tree_add {
  public:
    using value_type = T;

  private:
    int size_;
    std::vector<value_type> data_;

  public:
    fenwick_tree_add(){}
    fenwick_tree_add(int size): size_(size), data_(size + 1, 0){}

    void update(int i, value_type val){
      assert(0 <= i and i < size_);
      i += 1; // 1-index

      while(i <= size_){
        data_[i] = data_[i] + val;
        i += i & (-i);
      }
    }

    value_type fold(int i) const { // [0, i)
      assert(0 <= i and i <= size_);
      value_type ret = 0;

      while(i > 0){
        ret = ret + data_[i];
        i -= i & (-i);
      }

      return ret;
    }

    value_type fold(int l, int r) const { // [l, r)
      assert(0 <= l and l <= r and r <= size_);
      return fold(r) - fold(l);
    }

    value_type operator[](int x) const {
      return fold(x, x + 1);
    }
  };
}
#line 67 "main.cpp"


namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353 = 998244353;

  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  void solve(){
    int N; std::cin >> N;
    std::vector<int64_t> a(N), b(N); std::cin >> a >> b;
    compressor_builder<int64_t>().add(a, b).build().compress(a, b);

    int64_t ans = 0;
    std::sort(a.begin(), a.end());

    fenwick_tree_add<int64_t> s(2 * N);

    for(int i = 0; i < N; ++i){
      s.update(b[i], 1);
      ans += s.fold(a[i]);
    }

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

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
      std::cout << std::flush;
      std::cerr << std::flush;
    }catch(const std::istream::failure &e){
      break;
    }catch(...){
      break;
    }
  }
  return 0;
}
0