oj.uz

Submission #48947

# Submission time Handle Problem Language Result Execution time Memory
48947 2018-05-20T07:02:38 Z leehosu01 공장 (KOI13_factory) C++17
20 / 20
 630 ms 22024 KB 
#include<bits/stdc++.h>
using namespace std;
int um[1000001];
class FW{
    vector<int>F;
    int N;
public:
    FW(int k){F.assign((N=k)+1,0);}
    void in(int X,int Y){for(;X<=N;X+=X&-X)F[X]+=Y;}
    int out(int X){int sum=0;for(;X;X-=X&-X)sum+=F[X];return sum;}
};
int main()
{
    int  N;
    cin>>N;
    FW tr(N);
    vector<int>V(N);
    for(auto&I:V)cin>>I;
    for(int i=1;i<=N;i++)
    {
        int a;
        cin>>a;
        um[a]=i;
    }
    long long S=0;
    for(int i=0;i<N;i++)
    {
        S+=i-tr.out(um[V[i]]);
        tr.in(um[V[i]],1);
    }
    printf("%lld",S);
}

Subtask #1
2.2 / 2.2

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 672 KB Output is correct
4 Correct 3 ms 1516 KB Output is correct
5 Correct 4 ms 2012 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2976 KB Output is correct
2 Correct 9 ms 4384 KB Output is correct
3 Correct 16 ms 4512 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4736 KB Output is correct
2 Correct 55 ms 4900 KB Output is correct
3 Correct 72 ms 4984 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5316 KB Output is correct
2 Correct 164 ms 5740 KB Output is correct
3 Correct 210 ms 5996 KB Output is correct
4 Correct 310 ms 6812 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 427 ms 7664 KB Output is correct
2 Correct 498 ms 8376 KB Output is correct
3 Correct 630 ms 8428 KB Output is correct
4 Correct 572 ms 8560 KB Output is correct
5 Correct 562 ms 15212 KB Output is correct
6 Correct 494 ms 22024 KB Output is correct