結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2020-07-17 22:34:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#define all(x) (x).begin(), (x).end()typedef long long ll;#define MOD 1000000007using 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_treetemplate <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;}