No.3617 Swap
タグ : / 解いたユーザー数 21
作問者 :
kazuppa
/ テスター :
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 1 | 15 points | $N=2,\ M=1$ |
| Subtask 2 | 15 points | $M=1$ |
| Subtask 3 | 45 points | $N\leq 2000,\ M\leq 4000,\ T_i\leq M$ |
| Subtask 4 | 60 points | $T_i\leq M$ |
| Subtask 5 | 75 points | $T_i\leq M^2,\ Q\leq 500$ |
| Subtask 6 | 30 points | $N\leq 300,M=10^5,T_i\leq 10^{10}$ |
| Subtask 7 | 60 points | No 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もしくは右上の雲マークをクリックしてアカウントを作成してください。