codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1073B.md (2377B)


      1 Source: https://codeforces.com/problemset/problem/1073/B
      2 
      3 B. Vasya and Books
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 Help Vasya! Tell him the number of books he will put into his backpack during each step.
     26 
     27 Input
     28 
     29 The first line contains one integer $n~(1 \le n \le 2 \cdot 10^5)$ — the number of books in the stack.
     30 
     31 The second line contains $n$ integers $a_1, a_2, \dots, a_n~(1 \le a_i \le n)$ denoting the stack of books.
     32 
     33 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.
     34 
     35 All numbers $a_1 \dots a_n$ are distinct, the same goes for $b_1 \dots b_n$.
     36 
     37 Output
     38 
     39 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.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 1 2 3  
     48 2 1 3
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 2 0 1
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 5  
     61 3 1 4 2 5  
     62 4 5 1 3 2
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 3 2 0 0 0
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 6  
     75 6 5 4 3 2 1  
     76 6 5 3 4 2 1
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 1 1 2 0 1 1
     83 ```
     84 
     85 Note
     86 
     87 The first example is described in the statement.
     88 
     89 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.