Submission #14190

#	Time	Username	Problem	Language	Result	Execution time	Memory
14190		paulsohn	공장 (KOI13_factory)	C++98	20 / 20	263 ms	9084 KiB

factory

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
 
int N,D[1000001],FT[1048576];
long long S;
 
void add(int o, int d){
    if(o<1) return;
    FT[o]+=d;
    add(o>>1,d);
}
 
int calc(int L, int R){ //[L,R]
    int crumb=0,l=L>>1,r=R>>1;
    if(L>R) return 0;
    if(L==R) return FT[L];
    if(L&1){
        crumb+=FT[L];
        l=(L+1)>>1;
    }
    if(R&1==0){
        crumb+=FT[R];
        r=(R-1)>>1;
    }
    return crumb+calc(l,r);
}
 
int main(){
    int i,j,n;
    scanf("%d",&N);
    for(i=0;i<N;++i){
        scanf("%d",&n);
        D[n]=i;
    }
    for(i=0;i<N;++i){
        scanf("%d",&n);
        S+=calc(524288+D[n],524288+N);
        add(524288+D[n],1);
    }
    printf("%lld",S);
    return 0;
}

• 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