oj.uz

Submission #5376

# Submission time Handle Problem Language Result Execution time Memory
5376 2014-04-18T16:34:19 Z baneling100 공장 (KOI13_factory) C++
9.4 / 20
 216 ms 9412 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

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

void input(void)
{
    int i, temp;

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

void process(void)
{
    int 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 9412 KB Output is correct
2 Correct 0 ms 9412 KB Output is correct
3 Correct 0 ms 9412 KB Output is correct
4 Correct 0 ms 9412 KB Output is correct
5 Correct 0 ms 9412 KB Output is correct

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9412 KB Output is correct
2 Correct 24 ms 9412 KB Output is correct
3 Correct 32 ms 9412 KB Output is correct

Subtask #4
0.0 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9412 KB Output is correct
2 Incorrect 80 ms 9412 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 216 ms 9412 KB Output isn't correct
2 Halted 0 ms 0 KB -