No.1024 Children in a Row
タグ : / 解いたユーザー数 12
作問者 :
chocorusk
/ テスター :
Cinnamoroll
Problem Statement
$N$ children numbered $1, 2, \ldots , N$ are standing in a line in this order from the front. $M$ moves are about to be made. In the $i$-th move ($1\leq i\leq M$), person $a_i$ moves to the position immediately behind person $b_i$ (if there is someone behind person $b_i$, the moving person cuts in between them).
For each $i$ ($1\leq i\leq M$), find the number of the $k_i$-th person from the front in the final line when the $M$ moves are performed in order, skipping only the $i$-th one.
Input
$N\ M$ $a_1\ b_1\ k_1$ $a_2\ b_2\ k_2$ $:$ $a_M\ b_M\ k_M$
- $2\leq N, M\leq 2\times 10^5$
- $1\leq a_i, b_i, k_i\leq N$
- $a_i\neq b_i$
- All input values are integers.
Output
Print $M$ lines. On the $i$-th line ($1\leq i\leq M$), print the number of the $k_i$-th person from the front in the final line when the $M$ moves are performed in order, skipping only the $i$-th one.
Sample
Sample 1
Input
4 3 1 2 3 4 2 1 3 1 4
Output
2 2 3
- If the $1$-st move is skipped and only the $2$-nd and $3$-rd moves are performed, the line changes as $(1, 2, 3, 4)\to (1, 2, 4, 3)\to (1, 3, 2, 4)$. The number of the $3$-rd person from the front in this final line is $2$.
- If the $2$-nd move is skipped and only the $1$-st and $3$-rd moves are performed, the line changes as $(1, 2, 3, 4)\to (2, 1, 3, 4)\to (2, 1, 3, 4)$. The number of the $1$-st person from the front in this final line is $2$.
- If the $3$-rd move is skipped and only the $1$-st and $2$-nd moves are performed, the line changes as $(1, 2, 3, 4)\to (2, 1, 3, 4)\to (2, 4, 1, 3)$. The number of the $4$-th person from the front in this final line is $3$.
Sample 2
Input
2 3 2 1 2 2 1 1 1 2 1
Output
1 2 1
Sample 3
Input
9 8 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4
Output
1 9 1 7 9 5 3 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。