結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー QDSNQDSN
提出日時 2020-07-17 22:34:13
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 2,371 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 179,984 KB
実行使用メモリ 11,080 KB
最終ジャッジ日時 2023-08-20 02:12:33
合計ジャッジ時間 6,016 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 147 ms
10,312 KB
testcase_04 AC 175 ms
11,080 KB
testcase_05 AC 151 ms
10,132 KB
testcase_06 AC 134 ms
9,500 KB
testcase_07 AC 173 ms
10,824 KB
testcase_08 AC 6 ms
4,376 KB
testcase_09 AC 64 ms
7,372 KB
testcase_10 AC 111 ms
10,992 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 175 ms
10,772 KB
testcase_13 AC 170 ms
10,820 KB
testcase_14 AC 169 ms
10,804 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 11 ms
4,376 KB
testcase_24 AC 51 ms
5,988 KB
testcase_25 AC 122 ms
9,264 KB
testcase_26 AC 25 ms
4,608 KB
testcase_27 AC 66 ms
6,424 KB
testcase_28 AC 95 ms
7,584 KB
testcase_29 AC 136 ms
9,752 KB
testcase_30 AC 166 ms
10,632 KB
testcase_31 AC 34 ms
5,204 KB
testcase_32 AC 22 ms
4,380 KB
testcase_33 AC 131 ms
10,096 KB
testcase_34 AC 1 ms
4,380 KB
testcase_35 AC 1 ms
4,380 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 1 ms
4,380 KB
testcase_38 AC 2 ms
4,376 KB
testcase_39 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
template <typename Mnd> struct segment_tree {
    int sz;
    vector<Mnd> data;
    function<Mnd(Mnd, Mnd)> f;
    Mnd e;
    //サイズだけ指定して初期化
    segment_tree(int _sz, function<Mnd(Mnd, Mnd)> _f, Mnd _e) : f(_f), e(_e) {
        sz = 1;
        while(sz < _sz)
            sz <<= 1;
        data.assign(sz * 2, e);
    }
    //参照渡しなので代入とかもできる
    Mnd &operator[](const int &k) { return data[k + sz]; }
    //木を構築 O(n)
    void build() {
        for(int i = sz - 1; i > 0; i--)
            data[i] = f(data[2 * i], data[2 * i + 1]);
    }
    //更新しつつ木を再構築 O(log n)
    void update(int k, Mnd x) {
        data[k += sz] = x;
        while(k >>= 1)
            data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    //[a,b)でのクエリに答える　O(log n)
    Mnd query(int a, int b) const {
        Mnd l = e, r = e;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if(a & 1)
                l = f(l, data[a++]);
            if(b & 1)
                r = f(r, data[--b]);
        }
        return f(l, r);
    }
};
// 各項の順序を保ったまま最小値0,最大値size()-1以下にする
template <typename T> vector<T> simplify(vector<T> &a) {
    int n = a.size();
    vector<T> b = a;
    sort(b.begin(), b.end());
    vector<T> res(n);
    for(int i = 0; i < n; i++)
        res[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    return res;
}
// 転倒数を計算
// depend:segment_tree
template <typename T> long long inversion_number(vector<T> &a) {
    using lint = long long int;
    int n = a.size();
    vector<T> b = simplify(a);
    segment_tree<lint> count(
        n, [](lint a, lint b) { return a + b; }, 0);
    lint res = 0;
    for(int i = 0; i < n; i++) {
        res += count.query(b[i] + 1, n);
        count.update(b[i], count[b[i]] + 1);
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        mp[b[i]] = i;
    }
    for(int i = 0; i < n; i++) {
        a[i] = mp[a[i]];
    }
    cout << inversion_number(a) << endl;
}
0