結果
問題 | 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 1000000000000000000 template <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; }