結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:32:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 1,289 bytes |
コンパイル時間 | 1,523 ms |
コンパイル使用メモリ | 166,080 KB |
実行使用メモリ | 7,268 KB |
最終ジャッジ日時 | 2024-11-29 21:54:33 |
合計ジャッジ時間 | 2,848 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long long#define ii pair <int, int>#define app push_back#define all(a) a.begin(), a.end()#define bp __builtin_popcountll#define ll long long#define mp make_pair#define f first#define s second#define Time (double)clock()/CLOCKS_PER_SEC#define debug(x) std::cout << #x << ": " << x << '\n';const int N = 1e5+7;struct Fen {int f[N];void clear() {for (int i = 0; i < N; ++i) f[i] = 0;}void add(int i, int x) {for (; i < N; i |= i + 1)f[i] += x;}int get(int i) {int ans = 0;for (; i >= 0; i &= i + 1, --i) ans += f[i];return ans;}int get(int l, int r) {return get(r) - get(l - 1);}} f;int a[N], b[N], to[N];int bpos[N];signed main() {#ifdef HOMEfreopen("input.txt", "r", stdin);#else#define endl '\n'ios_base::sync_with_stdio(0); cin.tie(0);#endifint n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {cin >> b[i];bpos[b[i]] = i;}for (int i = 1; i <= n; ++i)to[i] = bpos[a[i]];int ans = 0;for (int i = n; i; --i) {ans += f.get(to[i]);f.add(to[i], 1);}cout << ans << endl;}