oj.uz

Submission #14190

# Submission time Handle Problem Language Result Execution time Memory
14190 2015-05-03T12:33:47 Z paulsohn 공장 (KOI13_factory) C++
20 / 20
 263 ms 9084 KB 
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
 
int N,D[1000001],FT[1048576];
long long S;
 
void add(int o, int d){
    if(o<1) return;
    FT[o]+=d;
    add(o>>1,d);
}
 
int calc(int L, int R){ //[L,R]
    int crumb=0,l=L>>1,r=R>>1;
    if(L>R) return 0;
    if(L==R) return FT[L];
    if(L&1){
        crumb+=FT[L];
        l=(L+1)>>1;
    }
    if(R&1==0){
        crumb+=FT[R];
        r=(R-1)>>1;
    }
    return crumb+calc(l,r);
}
 
int main(){
    int i,j,n;
    scanf("%d",&N);
    for(i=0;i<N;++i){
        scanf("%d",&n);
        D[n]=i;
    }
    for(i=0;i<N;++i){
        scanf("%d",&n);
        S+=calc(524288+D[n],524288+N);
        add(524288+D[n],1);
    }
    printf("%lld",S);
    return 0;
}

Subtask #1
2.2 / 2.2

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

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

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9084 KB Output is correct
2 Correct 63 ms 9084 KB Output is correct
3 Correct 89 ms 9084 KB Output is correct
4 Correct 114 ms 9084 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 199 ms 9084 KB Output is correct
2 Correct 231 ms 9084 KB Output is correct
3 Correct 174 ms 9084 KB Output is correct
4 Correct 263 ms 9084 KB Output is correct
5 Correct 204 ms 9084 KB Output is correct
6 Correct 253 ms 9084 KB Output is correct