Submission #2139

#	Time	Username	Problem	Language	Result	Execution time	Memory
2139		hana5505	공장 (KOI13_factory)	C++98	20 / 20	291 ms	18464 KiB

factory

#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
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8