제출 #7587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7587		jihoon	공장 (KOI13_factory)	C++98	20 / 20	256 ms	12996 KiB

factory

#include<cstdio>
int n;
int bit[1048577];
int num[1000001];
int idx[1000001];

void update(int idx){
    while(idx<=1048576){
        bit[idx]++;
        idx+=(idx & -idx);
    }
}

int sum(int idx){
    int hap=0;
    while(idx>0){
        hap+=bit[idx];
        idx-=(idx & -idx);
    }
    return hap;
}

int main(){
    int i,ia;
    long long int dap=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&ia);
        num[ia]=i+1;
    }
    for(i=0;i<n;i++){
        scanf("%d",&ia);
        dap+=i-sum(num[ia]);
        update(num[ia]);
    }
    printf("%lld",dap);
}

• 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