제출 #10074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
10074		gs14004	공장 (KOI13_factory)	C++98	20 / 20	228 ms	9016 KiB

factory

#include <cstdio>

int n, mp[1000005], t;
int c[500005];

struct f{
    int tree[530000], lim;
    void init(int n){
        for (lim = 1; lim <= n+1; lim <<= 1);
    }
    void add(int x){
        x++;
        while(x <= lim){
            tree[x]++;
            x += x & -x;
        }
    }
    int sum(int x){
        x++;
        int res = 0;
        while(x){
            res += tree[x];
            x -= x & -x;
        }
        return res;
    }
}bit;

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&t);
        mp[t] = i;
    }
    for (int i=0; i<n; i++) {
        scanf("%d",&t);
        c[mp[t]] = i;
    }
    bit.init(n);
    long long res = 0;
    for (int i=0; i<n; i++) {
        res += i - bit.sum(c[i]);
        bit.add(c[i]);
    }
    printf("%lld",res);
}

• 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