oj.uz

Submission #48948

# Submission time Handle Problem Language Result Execution time Memory
48948 2018-05-20T07:03:59 Z leehosu01 공장 (KOI13_factory) C++17
14.2 / 20
 1000 ms 22604 KB 
#include<bits/stdc++.h>
using namespace std;
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 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 3 ms 488 KB Output is correct
2 Correct 18 ms 752 KB Output is correct
3 Correct 16 ms 1084 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2192 KB Output is correct
2 Correct 109 ms 3252 KB Output is correct
3 Correct 179 ms 4320 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 234 ms 6116 KB Output is correct
2 Correct 447 ms 9276 KB Output is correct
3 Correct 580 ms 11512 KB Output is correct
4 Correct 955 ms 17084 KB Output is correct

Subtask #5
0 / 5.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 22604 KB Time limit exceeded
2 Halted 0 ms 0 KB -