oj.uz

Submission #1834

# Submission time Handle Problem Language Result Execution time Memory
1834 2013-07-18T03:36:00 Z alephnull 공장 (KOI13_factory) C++
20 / 20
 311 ms 14488 KB 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
long long merge(int *a,int *b,int n1,int n2,int *tmp){ 
    long long ret=0; 
    int i=0,ia=0,ib=0; 
    while(ia<n1&&ib<n2){ 
        if(a[ia]<=b[ib]) 
            tmp[i++]=a[ia++]; 
        else{ 
            tmp[i++]=b[ib++]; 
            ret+=n1-ia; 
        } 
    } 
    while(ia<n1) 
        tmp[i++]=a[ia++]; 
    while(ib<n2){ 
        tmp[i++]=b[ib++]; 
        ret+=n1-ia; 
    } 
    return ret; 
} 
long long rev(int* a,int n){ 
    if(n==1)return 0; 
    long long ret=0; 
    int a1[(n+1)/2],a2[n/2]; 
    for(int i=0;i<(n+1)/2;i++)a1[i]=a[i]; 
    for(int i=0;i<n/2;i++)a2[i]=a[(n+1)/2+i]; 
    ret+=rev(a1,(n+1)/2); 
    ret+=rev(a2,n/2); 
    ret+=merge(a1,a2,(n+1)/2,n/2,a); 
    return ret; 
} 
int main(){ 
    int n;scanf("%d",&n); 
    int a[n]; 
    int b[n]; 
    int* hash=new int[1000001]; 
    int p[n]; 
    for(int i=0;i<n;i++){ 
        scanf("%d",a+i); 
        hash[a[i]]=i; 
    } 
    for(int i=0;i<n;i++) 
        scanf("%d",b+i); 
    for(int i=0;i<n;i++) 
        p[hash[b[i]]]=i; 
    printf("%lld",rev(p,n)); 
}

Subtask #1
2.2 / 2.2

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5304 KB Output is correct
2 Correct 31 ms 5692 KB Output is correct
3 Correct 40 ms 6088 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6668 KB Output is correct
2 Correct 94 ms 7844 KB Output is correct
3 Correct 117 ms 8624 KB Output is correct
4 Correct 177 ms 10572 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 236 ms 12532 KB Output is correct
2 Correct 243 ms 14488 KB Output is correct
3 Correct 233 ms 14488 KB Output is correct
4 Correct 307 ms 14484 KB Output is correct
5 Correct 311 ms 14484 KB Output is correct
6 Correct 311 ms 14488 KB Output is correct