oj.uz

Submission #7587

# Submission time Handle Problem Language Result Execution time Memory
7587 2014-08-11T13:31:45 Z jihoon 공장 (KOI13_factory) C++
20 / 20
 256 ms 12996 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12996 KB Output is correct
2 Correct 0 ms 12996 KB Output is correct
3 Correct 0 ms 12996 KB Output is correct
4 Correct 0 ms 12996 KB Output is correct
5 Correct 0 ms 12996 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12996 KB Output is correct
2 Correct 0 ms 12996 KB Output is correct
3 Correct 4 ms 12996 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12996 KB Output is correct
2 Correct 20 ms 12996 KB Output is correct
3 Correct 28 ms 12996 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12996 KB Output is correct
2 Correct 76 ms 12996 KB Output is correct
3 Correct 96 ms 12996 KB Output is correct
4 Correct 144 ms 12996 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 180 ms 12996 KB Output is correct
2 Correct 212 ms 12996 KB Output is correct
3 Correct 208 ms 12996 KB Output is correct
4 Correct 252 ms 12996 KB Output is correct
5 Correct 256 ms 12996 KB Output is correct
6 Correct 252 ms 12996 KB Output is correct