結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:14:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 2,629 bytes |
コンパイル時間 | 1,858 ms |
コンパイル使用メモリ | 171,632 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-11-30 00:35:09 |
合計ジャッジ時間 | 4,261 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define lli long long int#define REP(i,s,n) for(lli i=s;i<n;i++)#define NUM 2520#define INF (1LL<<50)#define DEBUG 1#define mp(a,b) make_pair(a,b)#define SORT(V) sort(V.begin(),V.end())#define PI (3.141592653589794)#define TO_STRING(VariableName) # VariableName#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;template<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 (b < a) { a = b; return 1; } return 0; }/* https://qiita.com/drken/items/1b7e6e459c24a83bb7fd */template <class Abel> struct BIT {vector<Abel> dat;Abel UNITY_SUM = 0; // to be set/* [1, n] */BIT(lli n) { init(n); }void init(lli n) {dat.resize(n + 1);for (lli i = 0; i < (lli)dat.size(); ++i) dat[i] = UNITY_SUM;}/* a is 1-indexed */inline void add(lli a, Abel x) {for (lli i = a; i < (lli)dat.size(); i += i & -i)dat[i] = dat[i] + x;}/* [1, a], a is 1-indexed */inline Abel sum(lli a) {Abel res = UNITY_SUM;for (lli i = a; i > 0; i -= i & -i)res = res + dat[i];return res;}/* [a, b), a and b are 1-indexed */inline Abel sum(lli a, lli b) {return sum(b - 1) - sum(a - 1);}/* k-th number (k is 0-indexed) */lli get(long long k) {++k;lli res = 0;lli N = 1; while (N < (lli)dat.size()) N *= 2;for (lli i = N / 2; i > 0; i /= 2) {if (res + i < (lli)dat.size() && dat[res + i] < k) {k = k - dat[res + i];res = res + i;}}return res + 1;}};lli con[100100];void solve(){lli n;cin>>n;vector<lli> a(n),b(n);REP(i,0,n)cin>>a[i];REP(i,0,n){cin>>b[i];con[b[i]] = i+1;}REP(i,0,n){a[i] = con[a[i]];}lli ans = 0;BIT<lli> bits(n+10);REP(i,0,n){bits.add(a[i],1);ans += i+1-bits.sum(a[i]);}cout<<ans<<endl;}int main(){// cout << fixed << setprecision(5);lli t=1;//cin>>t;while(t--)solve();return 0;}