oj.uz

Submission #5377

# Submission time Handle Problem Language Result Execution time Memory
5377 2014-04-18T16:35:35 Z baneling100 공장 (KOI13_factory) C++
9.4 / 20
 252 ms 17736 KB 
#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

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17736 KB Output is correct
2 Correct 24 ms 17736 KB Output is correct
3 Correct 36 ms 17736 KB Output is correct

Subtask #4
0.0 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17736 KB Output is correct
2 Incorrect 84 ms 17736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.8

# Verdict Execution time Memory Grader output
1 Incorrect 252 ms 17736 KB Output isn't correct
2 Halted 0 ms 0 KB -