結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:28:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,155 bytes |
コンパイル時間 | 1,921 ms |
コンパイル使用メモリ | 199,132 KB |
最終ジャッジ日時 | 2025-01-11 22:11:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 1000000000000000000template <typename T>struct BIT{vector<T> v;int n;const T init_value = 0LL;BIT(int sz){n=sz+1;v.resize(n,init_value);}BIT(vector<T> &x){n=x.size()+1;v.resize(n,init_value);for(int i=0;i<x.size();i++){add(i,x[i]);}}void add(int x,T val){x++;while(x < n){v[x] = func(v[x],val);x += x & (-x);}}//区間[0,r)におけるクエリ処理T query(int r){T ret = init_value;while(r>0){ret = func(v[r],ret);r -= r & (-r);}return ret;}T query(int l,int r){return query(r) - query(l);}T func(T a,T b){return a+b;}};int main(){int N;cin>>N;vector<int> a(N),b(N);for(int i=0;i<N;i++){int t;cin>>t;a[t-1]=i;}vector<int> ind(N);for(int i=0;i<N;i++){cin>>b[i];b[i] = a[b[i]-1];ind[b[i]]=i;}BIT<long long> B(N);long long ans = 0LL;for(int i=0;i<N;i++){ans += B.query(ind[i],N);B.add(ind[i],1LL);}cout<<ans<<endl;return 0;}