oj.uz

Submission #10074

# Submission time Handle Problem Language Result Execution time Memory
10074 2014-10-08T11:56:50 Z gs14004 공장 (KOI13_factory) C++
20 / 20
 228 ms 9016 KB 
#include <cstdio>

int n, mp[1000005], t;
int c[500005];

struct f{
    int tree[530000], lim;
    void init(int n){
        for (lim = 1; lim <= n+1; lim <<= 1);
    }
    void add(int x){
        x++;
        while(x <= lim){
            tree[x]++;
            x += x & -x;
        }
    }
    int sum(int x){
        x++;
        int res = 0;
        while(x){
            res += tree[x];
            x -= x & -x;
        }
        return res;
    }
}bit;

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&t);
        mp[t] = i;
    }
    for (int i=0; i<n; i++) {
        scanf("%d",&t);
        c[mp[t]] = i;
    }
    bit.init(n);
    long long res = 0;
    for (int i=0; i<n; i++) {
        res += i - bit.sum(c[i]);
        bit.add(c[i]);
    }
    printf("%lld",res);
}

Subtask #1
2.2 / 2.2

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

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

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9016 KB Output is correct
2 Correct 64 ms 9016 KB Output is correct
3 Correct 88 ms 9016 KB Output is correct
4 Correct 132 ms 9016 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 188 ms 9016 KB Output is correct
2 Correct 200 ms 9016 KB Output is correct
3 Correct 192 ms 9016 KB Output is correct
4 Correct 228 ms 9016 KB Output is correct
5 Correct 220 ms 9016 KB Output is correct
6 Correct 212 ms 9016 KB Output is correct