Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

왼쪽에서 오른쪽으로 일렬로 배열된 $N$개의 광장이 있는 공원이 있으며, 순서대로 $0, 1, \dots, N - 1$의 번호가 매겨져 있습니다.

공원 안에는 $N$명의 사람이 있으며, 마찬가지로 $0, 1, \dots, N - 1$의 번호가 매겨져 있습니다. $0$ 이상 $N - 1$ 이하의 음이 아닌 정수들로 이루어진 수열 $X = (X_1, X_2, \dots, X_{|X|})$를 발표하면, 사람들은 다음 규칙에 따라 행진을 수행합니다:

  1. 각 $i = 0, 1, \dots, N - 1$에 대해, 사람 $i$는 광장 $i$로 이동합니다.
  2. 각 $j = 1, 2, \dots, |X|$에 대해, 이 순서대로 다음을 수행합니다:
    • 현재 광장 $X_j$에 있지 않은 모든 사람은 광장 $X_j$ 방향으로 정확히 한 칸 이동합니다.

$0$ 이상 $N - 1$ 이하의 정수로 이루어진 길이 $M$인 수열 $A = (A_0, A_1, \dots, A_{M-1})$이 주어집니다.

$Q$개의 온라인 질의에 답해야 합니다. 각 $i = 1, 2, \dots, Q$에 대해 정수 $t'_i, L'_i, R'_i, P'_i$가 주어집니다. 먼저 다음 과정을 통해 $t_i, L_i, R_i, P_i$를 복원하세요:

$\text{ans}_0 = 0$이라 하고, $\text{ans}_i$를 $i$번째 질의의 답이라고 합시다. $t_i, L_i, R_i, P_i$를 다음과 같이 복원합니다:

  • $t_i = ((t'_i + \text{ans}_{i-1}) \bmod 2)$
  • $a = ((L'_i + \text{ans}_{i-1}) \bmod M)$
  • $b = ((R'_i + \text{ans}_{i-1}) \bmod M)$
  • $L_i = \min(a, b)$
  • $R_i = \max(a, b)$
  • $P_i = ((P'_i + \text{ans}_{i-1}) \bmod N)$

여기서 음이 아닌 정수 $a$와 양의 정수 $b$에 대해, $(a \bmod b)$는 $a$를 $b$로 나눈 나머지를 나타내며 그 범위는 $0$부터 $b - 1$까지입니다.

복원된 각 $(t_i, L_i, R_i, P_i)$에 대해 다음 질의에 답하세요:

  • $t_i = 0$인 경우: $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$라고 합시다. 행진을 시뮬레이션하고 사람 $P_i$가 최종적으로 도달하는 광장의 번호를 출력합니다.
  • $t_i = 1$인 경우: $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$라고 합시다. 행진을 시뮬레이션하고 최종적으로 광장 $P_i$에 모이게 되는 사람의 수를 출력합니다.

입력

입력은 다음 형식으로 주어집니다:

N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
t'_2 L'_2 R'_2 P'_2
:
t'_Q L'_Q R'_Q P'_Q
  • 모든 입력값은 정수입니다.
  • $1 \le N, M, Q \le 2 \times 10^5$
  • $0 \le A_i \le N - 1$ ($0 \le i \le M - 1$)
  • $0 \le t'_i, t_i \le 1$ ($1 \le i \le Q$)
  • $0 \le L'_i, R'_i \le M - 1$ ($1 \le i \le Q$)
  • $0 \le L_i \le R_i \le M - 1$ ($1 \le i \le Q$)
  • $0 \le P'_i, P_i \le N - 1$ ($1 \le i \le Q$)

출력

$Q$개의 줄을 출력합니다. 각 $i = 1, 2, \dots, Q$에 대해 $i$번째 질의의 답인 $\text{ans}_i$를 출력합니다.

예제

예제 입력 1

4 5 3
0 2 3 2 1
0 1 3 2
1 0 2 1
1 4 4 1

예제 출력 1

2
0
3

예제 입력 2

7 4 1
3 3 3 3
1 3 0 3

예제 출력 2

7

노트

예제 1의 첫 번째 질의에서 $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$이고 $X = (2, 3, 2)$일 때, 사람 $2$는 $2 \to 2 \to 3 \to 2$로 이동하므로 답은 $2$입니다.

예제 1의 두 번째 질의에서 $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$이고 $X = (3, 2, 1)$일 때, 마지막에 광장 $3$에 있는 사람의 수는 $0$입니다.

예제 1의 세 번째 질의에서 $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$이고 $X = (1)$일 때, 마지막에 광장 $1$에 있는 사람의 수는 $3$입니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.