Vasya and Books (Codeforces 1073B)
Tags: Implement, math

Vasya has got $$$n$$$ books, numbered from $$$1$$$ to $$$n$$$, arranged in a stack. The topmost book has number $$$a_1$$$, the next one — $$$a_2$$$, and so on. The book at the bottom of the stack has number $$$a_n$$$. All numbers are distinct.Vasya wants to move all the books to his backpack in $$$n$$$ steps. During $$$i$$$-th step he wants to move the book number $$$b_i$$$ into his backpack. If the book with number $$$b_i$$$ is in the stack, he takes this book and all the books above the book $$$b_i$$$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $$$[1, 2, 3]$$$ (book $$$1$$$ is the topmost), and Vasya moves the books in the order $$$[2, 1, 3]$$$, then during the first step he will move two books ($$$1$$$ and $$$2$$$), during the second step he will do nothing (since book $$$1$$$ is already in the backpack), and during the third step — one book (the book number $$$3$$$). Note that $$$b_1, b_2, \dots, b_n$$$ are distinct.Help Vasya! Tell him the number of books he will put into his backpack during each step.

Input: The first line contains one integer $$$n~(1 \le n \le 2 \cdot 10^5)$$$ — the number of books in the stack.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(1 \le a_i \le n)$$$ denoting the stack of books.The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n~(1 \le b_i \le n)$$$ denoting the steps Vasya is going to perform.All numbers $$$a_1 \dots a_n$$$ are distinct, the same goes for $$$b_1 \dots b_n$$$.

Output: Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of books Vasya moves to his backpack during the $$$i$$$-th step.

Note: The first example is described in the statement.In the second example, during the first step Vasya will move the books $$$[3, 1, 4]$$$. After that only books $$$2$$$ and $$$5$$$ remain in the stack ($$$2$$$ is above $$$5$$$). During the second step Vasya will take the books $$$2$$$ and $$$5$$$. After that the stack becomes empty, so during next steps Vasya won't move any books.

Sample Inputs:
3
1 2 3
2 1 3

5
3 1 4 2 5
4 5 1 3 2

6
6 5 4 3 2 1
6 5 3 4 2 1

Sample Outputs:
2 0 1

3 2 0 0 0

1 1 2 0 1 1

Solution (Python):
n = int(input())
a = input().split()
s = {}
x = 0
res = ''
for i in input().split():
    if i in s:
        res += '0 '
    else:
        for j in range(x, n):
            if a[j] == i:
                break
            s[a[j]] = None
        idx = j + 1
        res += str(idx - x) + ' '
        x = idx
print(res)

Solution (Python):
def vasya_and_books(n, stack, steps):
    positions = {book: pos for (pos, book) in enumerate(stack)}
    current_top = 0
    result = []
    for book in steps:
        if positions[book] >= current_top:
            moved_books = positions[book] - current_top + 1
            result.append(moved_books)
            current_top = positions[book] + 1
        else:
            result.append(0)
    return result
n = int(input().strip())
stack = list(map(int, input().strip().split()))
steps = list(map(int, input().strip().split()))
result = vasya_and_books(n, stack, steps)
print(' '.join(map(str, result)))

Solution (Python):
end = int(input())
books = input().split()
removed = {}
beginning = 0
output = ''
for book in input().split():
    if book in removed:
        output += '0 '
    else:
        for i in range(beginning, end):
            if books[i] == book:
                break
            removed[books[i]] = None
        index = i + 1
        output += str(index - beginning) + ' '
        beginning = index
print(output)