# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
3142 | club4208 | 공장 (KOI13_factory) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define MAXN 500001
int up[MAXN], down[MAXN], dt[MAXN], hash[1000001];
int idx_tree[1048576], n, trs;
int getsum(int a, int b){
int sum=0; a=trs/2+a-1; b=trs/2+b-1;
while(a<=b){
if(a%2==1){ sum+=idx_tree[a]; a++; }
if(b%2==0){ sum+=idx_tree[b]; b--; }
a/=2;
b/=2;
}
return sum;
}
void add(int a){
a=trs/2+a-1;
while(a>=1){
idx_tree[a]++;
a/=2;
}
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt', "w", stdout);
scanf("%d", &n);
int i, max=0;
for(i=1;i<=n;i++){
scanf("%d", &up[i]);
hash[up[i]]=i;
}
for(i=1;i<=n;i++){
scanf("%d", &down[i]);
dt[i]=hash[down[i]];
}
trs=1;
while(trs<n){
trs*=2;
}
trs*=2;
long long int sum=0;
for(i=1;i<=n;i++){
sum+=getsum(dt[i], n);
add(dt[i]);
if(max<dt[i]) max=dt[i];
}
printf("%lld", sum);
return 0;
}