結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:39:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 2,359 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 201,684 KB |
最終ジャッジ日時 | 2025-01-11 22:26:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<double, double> pdd;typedef vector<ll> vl;typedef vector<vector<ll>> vvl;//typedef vector<vector<ll>> Graph;const ll mod = 1e9 + 7;//const ll mod = 998244353;#define REP(i,n) for(ll i=0;i<(ll)n;i++)#define dump(x) cerr << #x << " = " << (x) << endl;#define spa << " " <<#define fi first#define se secondtemplate<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}template<class T> ostream& operator << (ostream& os, const vector<T> v){for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;}template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;}template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++){cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];for(ll i=1;i<n;i++)cerr spa v[i];cerr<<endl;};template<class V, int ME> class BIT {public:V bit[1<<ME];V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}};BIT<int, 18> bi;ll count_inversion(vector<ll> &a, int s, int t){////!!!!!!!! BIT をでかく取りすぎるとTLE·するので適切に長さを変える!! !!!!!!!!!////////// [s, t](閉区間)の転倒数を求めるREP(i, 1<<18) bi.bit[i] = 0;ll res = 0;for(int i=t;i>s-1;i--){res+=bi.total(a[i]);bi.update(a[i], 1);}return res;}int main(){cin.tie(0);ios::sync_with_stdio(false);ll n;cin >> n;vector<ll> a(n), b(n), c(n);map<ll, ll> mp;REP(i, n) cin >> a[i];REP(i, n) cin >> b[i];REP(i, n) mp[a[i]] = i+1;REP(i, n) c[i] = mp[b[i]];ll res = count_inversion(c, 0, n-1);cout << res << endl;return 0;}