Submission #48947

#	Time	Username	Problem	Language	Result	Execution time	Memory
48947		leehosu01	공장 (KOI13_factory)	C++17	20 / 20	630 ms	22024 KiB

factory

#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
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8