oj.uz

Submission #48946

# Submission time Handle Problem Language Result Execution time Memory
48946 2018-05-20T07:01:18 Z leehosu01 공장 (KOI13_factory) C++17
14.2 / 20
 1000 ms 67112 KB 
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>um;
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 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 584 KB Output is correct
5 Correct 3 ms 700 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 9 ms 940 KB Output is correct
3 Correct 15 ms 1320 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3264 KB Output is correct
2 Correct 75 ms 4464 KB Output is correct
3 Correct 133 ms 6836 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 164 ms 9340 KB Output is correct
2 Correct 293 ms 14600 KB Output is correct
3 Correct 378 ms 18768 KB Output is correct
4 Correct 592 ms 28568 KB Output is correct

Subtask #5
0 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 752 ms 38088 KB Output is correct
2 Correct 913 ms 53796 KB Output is correct
3 Correct 956 ms 60492 KB Output is correct
4 Execution timed out 1022 ms 67112 KB Time limit exceeded
5 Halted 0 ms 0 KB -