Submission #3143

#	Time	Username	Problem	Language	Result	Execution time	Memory
3143		club4208	공장 (KOI13_factory)	C++98	20 / 20	304 ms	14948 KiB

factory

#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;
}

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8