結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2020-07-17 21:46:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,654 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 177,168 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-11-29 23:03:10 |
合計ジャッジ時間 | 4,797 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)using namespace std;using ll = long long ;using P = pair<int,int> ;using pll = pair<long long,long long>;constexpr int INF = 1e9;constexpr long long LINF = 1e17;constexpr int MOD = 1000000007;constexpr double PI = 3.14159265358979323846;//1-indexedに注意!!!struct BIT{private:int n,n_;vector<long long> bit;public:BIT(int n):n(n){bit.resize(n+1);n_ = 1;while(n_<=n) n_<<=1;n_ >>= 1;}//1-indexlong long sum(int i){long long res = 0;while(i > 0){res += bit[i];i -= i&-i;}return res;}//1-indexvoid add(int i,long long val){while(i <= n){bit[i] += val;i += i&-i;}}//return 1-indexint lowerbound(long long w){if(w <= 0) return 0;int x = 0;for(int k=n_;k>0;k>>=1){if(x+k<=n&&bit[x+k]<w){w -= bit[x+k];x += k;}}return x+1;}};int main(){int n;cin >> n;vector<int> a(n),b(n);rep(i,n) cin >> a[i];rep(i,n) cin >> b[i];map<int,int> mp;rep(i,n) mp[b[i]] = i;vector<int> v(n);rep(i,n){v[i] = mp[a[i]];}BIT bit(n);ll ans = 0;rep(i,n){ans += i-bit.sum(v[i]+1);bit.add(v[i]+1,1);}cout << ans << endl;return 0;}