結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー QDSNQDSN
提出日時 2020-07-17 22:34:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 2,371 bytes
コンパイル時間 2,176 ms
コンパイル使用メモリ 182,728 KB
実行使用メモリ 11,188 KB
最終ジャッジ日時 2024-11-30 01:26:02
合計ジャッジ時間 6,289 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 140 ms
10,352 KB
testcase_04 AC 161 ms
11,112 KB
testcase_05 AC 137 ms
10,200 KB
testcase_06 AC 125 ms
9,908 KB
testcase_07 AC 163 ms
11,064 KB
testcase_08 AC 7 ms
5,248 KB
testcase_09 AC 67 ms
7,656 KB
testcase_10 AC 118 ms
11,184 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 161 ms
11,032 KB
testcase_13 AC 164 ms
11,188 KB
testcase_14 AC 163 ms
11,180 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 12 ms
5,248 KB
testcase_24 AC 52 ms
6,272 KB
testcase_25 AC 116 ms
9,668 KB
testcase_26 AC 26 ms
5,248 KB
testcase_27 AC 65 ms
6,868 KB
testcase_28 AC 92 ms
7,808 KB
testcase_29 AC 125 ms
9,860 KB
testcase_30 AC 153 ms
10,880 KB
testcase_31 AC 35 ms
5,248 KB
testcase_32 AC 23 ms
5,248 KB
testcase_33 AC 123 ms
10,408 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 2 ms
5,248 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