結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー ok
提出日時 2020-07-17 21:49:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 1,516 bytes
コンパイル時間 809 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-11-29 23:13:17
合計ジャッジ時間 2,518 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define int long long
#define endl "\n"
constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007;
struct fast_io {
fast_io(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
};
} fio;
class BIT{
vector<int> bit;
public:
BIT(){
}
BIT(int size){
init(size);
}
void init(int size){
bit.clear();
bit.resize(size+1);
}
int sum(int i){
int s = 0;
while(i > 0){
s += bit[i];
i -= i & -i;
}
return s;
}
void add(int i , int x){
while(i < bit.size()){
bit[i] += x;
i += i & -i;
}
}
int lower_bound(int w){
if(w <= 0) return 0;
int x = 0, t = 1;
while(t*2 < bit.size()) t *= 2;
for(int k = t; k > 0; k /= 2){
if(x + k < bit.size() && bit[x + k] < w){
w -= bit[x + k];
x += k;
}
}
return x + 1;
}
};
signed main(){
cout<<fixed<<setprecision(10);
int n;
int ans = 0;
vector<int> a, b, c;
BIT bit;
cin>>n;
a.resize(n);
b.resize(n);
c.resize(n);
bit.init(n+3);
for(int i = 0; i < n; i++){
cin>>a[i];
}
for(int i = 0; i < n; i++){
int x;
cin>>x;
b[x-1] = n - (i);
}
for(int i = 0; i < n; i++){
c[i] = b[a[i]-1];
// cout<<c[i]<<endl;
}
for(int i = 0; i < n; i++){
ans += bit.sum(c[i]);
// cout<<"i = "<<c[i]<<" "<<bit.sum(i+1)<<endl;
bit.add(c[i], 1);
}
cout<<ans<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0