oj.uz

Submission #2685

# Submission time Handle Problem Language Result Execution time Memory
2685 2013-07-30T15:18:00 Z ladown21 공장 (KOI13_factory) C++
20 / 20
 232 ms 12804 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12804 KB Output is correct
2 Correct 0 ms 12804 KB Output is correct
3 Correct 0 ms 12804 KB Output is correct
4 Correct 0 ms 12804 KB Output is correct
5 Correct 0 ms 12804 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12804 KB Output is correct
2 Correct 4 ms 12804 KB Output is correct
3 Correct 4 ms 12804 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12804 KB Output is correct
2 Correct 24 ms 12804 KB Output is correct
3 Correct 20 ms 12804 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12804 KB Output is correct
2 Correct 56 ms 12804 KB Output is correct
3 Correct 84 ms 12804 KB Output is correct
4 Correct 128 ms 12804 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 180 ms 12804 KB Output is correct
2 Correct 200 ms 12804 KB Output is correct
3 Correct 188 ms 12804 KB Output is correct
4 Correct 220 ms 12804 KB Output is correct
5 Correct 232 ms 12804 KB Output is correct
6 Correct 216 ms 12804 KB Output is correct