問題一覧 > 通常問題

No.3617 Swap

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 21
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
お気に入りにしたユーザー ProblemId : 13649 / 自分の提出
問題文最終更新日: 2026-08-06 13:48:58
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
Paken新入生コンday1 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,M$ and integer sequences $(L_1,L_2,\dotsc,L_M),(R_1,R_2,\dotsc,R_M)$ consisting of integers between $1$ and $N$, inclusive.

Consider the following problem.

There is a sequence $(A_1,A_2,...,A_N)$ of length $N$. Initially, $A_i=i$.

For $k=1,2,\dotsc,t$ in this order, perform the operation of swapping the $L_{((k-1)\bmod M)+1}$-th and $R_{((k-1)\bmod M)+1}$-th elements of $A$. Find $A_x$ after these operations.

There are $Q$ situations to consider for this problem. For the $i$-th situation, answer the above problem with $t=T_i,x=X_i$.

Constraints

  • $2\leq N\leq 10^5$
  • $1\leq M,Q\leq 2\times 10^5$
  • $1\leq L_i< R_i\leq N$
  • $1\leq X_i\leq N$
  • $1\leq T_i\leq 10^{18}$
  • All input values are integers.

Subtasks

This problem has partial scoring by subtasks.

Subtask Score Constraints
Subtask 115 points$N=2,\ M=1$
Subtask 215 points$M=1$
Subtask 345 points$N\leq 2000,\ M\leq 4000,\ T_i\leq M$
Subtask 460 points$T_i\leq M$
Subtask 575 points$T_i\leq M^2,\ Q\leq 500$
Subtask 630 points$N\leq 300,M=10^5,T_i\leq 10^{10}$
Subtask 760 pointsNo additional constraints

Input

$N\ M\ Q$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_M\ R_M$
$T_1\ X_1$
$T_2\ X_2$
$\vdots$
$T_Q\ X_Q$

Output

Output $Q$ lines.

On the $i\ (1\leq i\leq Q)$-th line, output the answer for the $i$-th situation.

Sample

Sample 1
Input
5 3 3
1 2
3 4
4 5
4 3
2 4
8 1
Output
4
3
2

Consider the $1$-st situation.

Initially, $A=(1,2,3,4,5)$.

After the operation for $k=1$, $A=(2,1,3,4,5)$; after $k=2$, $A=(2,1,4,3,5)$; after $k=3$, $A=(2,1,4,5,3)$; after $k=4$, $A=(1,2,4,5,3)$.

Therefore, the answer for situation $1$ is $4$.

This case satisfies the constraints of Subtasks 5,6,7.

Sample 2
Input
2 1 2
1 2
1 1
2 1
Output
2
1

This case satisfies the constraints of Subtasks 1,2,5,6,7.

Sample 3
Input
6 5 3
1 6
2 6
2 3
4 5
3 4
2 1
5 1
1 1
Output
6
6
6

This case satisfies the constraints of Subtasks 3,4,5,6,7.

Sample 4
Input
1000 5 6
159 314
159 411
411 892
169 231
29 159
314159 314
159411 159
411892 411
169231 169
29159 29
1000000000000000000 1
Output
29
29
411
169
411
1

This case satisfies the constraints of Subtasks 6,7.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。