Nombre d'elements menors o iguals a l'altra llista X25375

Statement

thehtml

Cada cas d’entrada d’aquest exercici comença amb un natural positiu n en una primera línia. En una segona línia hi ha una llista de n enters u₁,…,u_n ordenats creixentment (no necessàriament de forma estricta, de manera que hi poden haver repeticions). En una tercera línia hi ha una llista de n enters v₁,…,v_n ordenats creixentment (no necessàriament de forma estricta, de manera que hi poden haver repeticions).

La sortida de cada cas escriu n naturals c₁,…,c_n en una línia. Donat un i de 1,…,n, el natural c_i és el nombre de valors de v₁,…,v_n que son menors o iguals a u_i.

Per exemple, considereu aquest cas d’entrada:

10
1 1 2 4 6 6 6 7 9 9
0 1 3 3 3 4 5 7 7 8

Amb l’entrada anterior, la sortida ha de ser:

2 2 2 6 7 7 7 9 10 10

Entrada

L’entrada té varis casos. Cada cas comença amb un natural positiu n en una primera línia. Després venen n enters u₁,…,u_n en una línia, ordenats creixentment (no necessàriament estríctament). Després venen n enters v₁,…,v_n en una línia, ordenats creixentment (no necessàriament estríctament).

Sortida

Per a cada cas, el programa ha d’escriure n naturals c₁,…,c_n en una línia. El natural c_i és el nombre de valors v₁,…,v_n que son menors o iguals a u_i.

Observació

Avaluació sobre 10 punts:

Solució lenta: 5 punts.
Solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal (acceptem també nlogn com a solució ràpida) i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

Public test cases

Input

4
1 6 8 8
2 4 7 8
2
5 6
6 8
4
1 5 7 8
2 7 9 9
10
1 1 2 2 4 5 6 9 9 9
1 1 2 3 4 5 6 7 8 8
5
3 3 4 5 6
2 2 3 9 9
4
5 5 6 6
1 6 7 7
7
1 1 3 4 5 8 9
1 1 3 3 6 7 7
1
8
7
7
2 3 4 6 7 9 9
1 2 2 7 7 8 9
7
1 2 2 3 3 4 9
1 3 3 4 6 7 8
2
3 9
2 7
10
1 2 3 3 4 5 5 6 7 7
1 3 4 4 5 5 6 6 7 8
10
1 1 2 3 3 3 4 4 8 9
2 3 3 3 4 5 5 6 7 7
6
2 3 6 6 8 9
2 5 5 7 8 9
8
1 1 5 5 7 8 9 9
2 3 3 4 6 8 9 9
6
2 3 4 6 8 9
1 2 3 4 7 7
4
3 6 8 9
4 5 8 8
9
1 1 3 3 3 4 7 7 9
2 2 3 3 3 3 6 7 8
10
1 3 3 4 5 6 7 8 9 9
2 4 4 5 5 5 6 6 7 9
2
5 7
6 8

Output

0 2 4 4
0 1
0 1 2 2
2 2 3 3 5 6 7 10 10 10
3 3 3 3 3
1 1 2 2
2 2 4 4 4 7 7
1
3 3 3 3 5 7 7
1 1 1 3 3 4 7
1 2
1 1 2 2 4 6 6 8 9 9
0 0 1 4 4 4 5 5 10 10
1 1 3 3 5 6
0 0 4 4 5 6 8 8
2 3 4 4 6 6
0 2 4 4
0 0 6 6 6 6 8 8 9
0 1 1 3 6 8 9 9 10 10
0 1

Information

Author: PRO1
Language: Catalan
Official solutions: C++
User solutions: C++