結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー QDSN
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0