結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2022-07-11 11:54:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,890 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 196,240 KB |
最終ジャッジ日時 | 2025-01-30 06:24:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vvvvll = vector<vvvll>;using vb = vector<bool>;using vvb = vector<vb>;using vvvb = vector<vvb>;using vvvvb = vector<vvvb>;using vd = vector<double>;using vvd = vector<vd>;using vvvd = vector<vvd>;#define all(A) A.begin(),A.end()#define ALL(A) A.begin(),A.end()#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)using pqr = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>;template<class T>bool chmax(T& p, T q, bool C = 1) {if (C == 0 && p == q) {return 1;}if (p < q) {p = q;return 1;}else {return 0;}}template<class T>bool chmin(T& p, T q, bool C = 1) {if (C == 0 && p == q) {return 1;}if (p > q) {p = q;return 1;}else {return 0;}}ll gcd(ll(a), ll(b)) {if (b == 0)return a;ll c = a;while (a % b != 0) {c = a % b;a = b;b = c;}return b;}struct fenwick_tree {ll n;vll bit;fenwick_tree(ll num) :bit(num + 1, 0) { n = num; }void add(ll i, ll w) {for (ll x = i+1; x <= n; x += x & -x) {bit[x-1] += w;}}ll sum(ll i) {ll ret = 0;for (ll x = i+1; x > 0; x -= x & -x) {ret += bit[x-1];}return ret;}ll sum(ll L, ll R) {return sum(R) - sum(L);}};ll TE(vll A) {ll res = 0;ll N = A.size();fenwick_tree fw(N);rep(i, N) {res += i - fw.sum(A[i]);fw.add(A[i], 1);}return res;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);ll N;cin>>N;vll A(N),B(N);rep(i,N){ll P;cin>>P;A[P-1]=i;}rep(i,N){ll Q;cin>>Q;B[i]=A[Q-1];}cout<<TE(B)<<endl;}