Submission #5377

#	Time	Username	Problem	Language	Result	Execution time	Memory
5377		baneling100	공장 (KOI13_factory)	C++98	9.40 / 20	252 ms	17736 KiB

factory

#include <stdio.h>
#include <algorithm>

using namespace std;

pair <long long,long long> a[500001];
long long n, check[1000001], idx[131073], nn, ans;

void input(void)
{
    long long i, temp;

    scanf("%lld",&n);
    for(i=1 ; i<=n ; i++)
    {
        scanf("%lld",&temp);
        check[temp]=i;
    }
    for(i=1 ; i<=n ; i++)
    {
        scanf("%lld",&temp);
        a[i]=make_pair(check[temp],i);
    }
    sort(a+1,a+n+1);
    for(nn=1 ; nn<n ; nn*=2);
}

void process(void)
{
    long long i, temp, hab;

    for(i=n ; i>=1 ; i--)
    {
        temp=a[i].second-1;
        hab=0;
        while(temp>0)
        {
            hab+=idx[temp];
            temp&=~(~temp+1);
        }
        ans+=hab;
        temp=a[i].second;
        while(temp<=nn)
        {
            idx[temp]++;
            temp+=temp&(~temp+1);
        }
    }
}

void output(void)
{
    printf("%lld",ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 0 / 4.8
• Subtask 5: 0 / 5.8