oj.uz

답안 #2139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2139 2013-07-20T03:00:45 Z hana5505 공장 (KOI13_factory) C++
20 / 20
 291 ms 18464 KB 
#include<stdio.h> 
int si[1000001]; 
int ar[500001][2]; 
int l[500001][2]; 
int r[500001][2]; 
int ans[500001],n; 
void sort(int s,int e)   
{   
    int mid=(s+e)/2;   
    int lhead,rhead,point,i;   
      
    if(e-s>1){   
        sort(s,mid);   
        sort(mid+1,e);   
    }   
    for(i=s;i<=mid;i++){   
        l[i][0]=ar[i][0];   
        l[i][1]=ar[i][1];   
    }   
    for(i=mid+1;i<=e;i++){   
        r[i][0]=ar[i][0];   
        r[i][1]=ar[i][1];   
    }   
    point=lhead=s;   
    rhead=mid+1;   
    while(point<=e){   
        if(lhead>mid){   
            ar[point][0]=r[rhead][0];   
            ar[point++][1]=r[rhead++][1];   
        }   
        else if(rhead>e){   
            ar[point][0]=l[lhead][0];   
            ar[point++][1]=l[lhead++][1];   
        }   
        else{   
            if(l[lhead][0]<r[rhead][0]){   
                ar[point][0]=l[lhead][0];   
                ar[point++][1]=l[lhead++][1];   
            }   
            else{   
                ar[point][0]=r[rhead][0];   
                ar[point++][1]=r[rhead][1];   
                ans[ar[rhead][1]]+=(mid-lhead)+1;   
                rhead++;   
            }   
        }   
    }   
}   
int main() 
{ 
    long long s=0; 
    int i,t,st,tmp; 
  
    scanf("%d",&n); 
  
    for(i=1;i<=n;i++) 
        scanf("%d",&ar[i][0]); 
    for(i=1;i<=n;i++){ 
        scanf("%d",&t); 
        si[t]=i; 
    } 
    if(n==1){ 
        printf("0"); 
        return 0; 
    } 
    for(i=1;i<=n;i++){ 
        ar[i][0]=si[ar[i][0]]; 
        ar[i][1]=i; 
        ans[i]=1; 
    } 
    sort(1,n); 
    for(i=1;i<=n;i++) 
        s+=ans[i]-1; 
  
    printf("%lld",s); 
}

Subtask #1
2.2 / 2.2

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18464 KB Output is correct
2 Correct 0 ms 18464 KB Output is correct
3 Correct 0 ms 18464 KB Output is correct
4 Correct 0 ms 18464 KB Output is correct
5 Correct 0 ms 18464 KB Output is correct

Subtask #2
3.4 / 3.4

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18464 KB Output is correct
2 Correct 3 ms 18464 KB Output is correct
3 Correct 4 ms 18464 KB Output is correct

Subtask #3
3.8 / 3.8

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 18464 KB Output is correct
2 Correct 21 ms 18464 KB Output is correct
3 Correct 37 ms 18464 KB Output is correct

Subtask #4
4.8 / 4.8

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 18464 KB Output is correct
2 Correct 87 ms 18464 KB Output is correct
3 Correct 108 ms 18464 KB Output is correct
4 Correct 170 ms 18464 KB Output is correct

Subtask #5
5.8 / 5.8

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 18464 KB Output is correct
2 Correct 219 ms 18464 KB Output is correct
3 Correct 220 ms 18464 KB Output is correct
4 Correct 283 ms 18464 KB Output is correct
5 Correct 287 ms 18464 KB Output is correct
6 Correct 291 ms 18464 KB Output is correct