Submission #2685

#	Time	Username	Problem	Language	Result	Execution time	Memory
2685		ladown21	공장 (KOI13_factory)	C++98	20 / 20	232 ms	12804 KiB

factory

#include <stdio.h>

const int MAX = 1000010;

int A[MAX],B[MAX], T[MAX];

int Sum(int e)
{
	int r=0;
	while (e>0)
		r+=T[e], e-=e&-e;
	return r;
}
void Update(int e, int v, int N)
{
	while (e<=N)
		T[e]+=v, e+=e&-e;
}
int main()
{
	int N,M;
	scanf("%d",&N);

	for (int i=1; i<=N; i++) {
		scanf("%d",&M);
		A[M] = i;
	}
	for (int i=1; i<=N; i++) {
		scanf("%d",&M);
		B[A[M]] = i;
	}
	long long ret=0;
	for (int i=1; i<=N; i++) {
		ret += i-Sum(B[i])-1;
		Update(B[i],1,N);
	}
	printf("%lld\n",ret);
}

• 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