oj.uz

Submission #3143

# Submission time Handle Problem Language Result Execution time Memory
3143 2013-08-26T07:49:14 Z club4208 공장 (KOI13_factory) C++
20 / 20
 304 ms 14948 KB 
#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

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14948 KB Output is correct
2 Correct 24 ms 14948 KB Output is correct
3 Correct 32 ms 14948 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14948 KB Output is correct
2 Correct 84 ms 14948 KB Output is correct
3 Correct 108 ms 14948 KB Output is correct
4 Correct 164 ms 14948 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 216 ms 14948 KB Output is correct
2 Correct 240 ms 14948 KB Output is correct
3 Correct 272 ms 14948 KB Output is correct
4 Correct 304 ms 14948 KB Output is correct
5 Correct 268 ms 14948 KB Output is correct
6 Correct 280 ms 14948 KB Output is correct