問題一覧 > 通常問題

No.1024 Children in a Row

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : chocorusk / テスター : Cinnamoroll
お気に入りにしたユーザー ProblemId : 4034 / 自分の提出
問題文最終更新日: 2020-04-11 00:17:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 243 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。