oj.uz

Submission #5378

# Submission time Handle Problem Language Result Execution time Memory
5378 2014-04-18T16:37:12 Z baneling100 공장 (KOI13_factory) C++
20 / 20
 284 ms 12996 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

pair <int,int> a[500001];
int n, check[1000001], idx[1048576], 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 12996 KB Output is correct
2 Correct 0 ms 12996 KB Output is correct
3 Correct 0 ms 12996 KB Output is correct
4 Correct 0 ms 12996 KB Output is correct
5 Correct 0 ms 12996 KB Output is correct

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

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

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12996 KB Output is correct
2 Correct 80 ms 12996 KB Output is correct
3 Correct 112 ms 12996 KB Output is correct
4 Correct 156 ms 12996 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 220 ms 12996 KB Output is correct
2 Correct 216 ms 12996 KB Output is correct
3 Correct 224 ms 12996 KB Output is correct
4 Correct 284 ms 12996 KB Output is correct
5 Correct 284 ms 12996 KB Output is correct
6 Correct 268 ms 12996 KB Output is correct