結果

問題 No.1115 二つの数列 / Two Sequences
コンテスト
ユーザー yuui
提出日時 2020-07-17 22:11:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 946 bytes
コンパイル時間 2,078 ms
コンパイル使用メモリ 203,784 KB
最終ジャッジ日時 2025-01-11 22:46:09
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};


int main() {
    ll N;
    cin >> N;
    vector<ll> A(N),B(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    unordered_map<ll,ll> Bmp; 
    for(int i=0;i<N;i++){
        ll B;
        cin >> B;
        Bmp[B] = i;
    }
    unordered_map<ll,ll> revA;
    for(int i=0;i<N;i++){
        A[i] = Bmp[A[i]];
        revA[A[i]] = i;
    }

    ll ans =0;
    BinaryIndexedTree<ll> bit(N+5);
    for(int i=0;i<N;i++){
        ans += (bit.sum(N-1) -bit.sum(revA[i]));
        bit.add(revA[i],1);
    }
    
    cout << ans << endl;


    return 0;
}
0