Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Il y a un parc comportant $N$ places disposées en ligne de gauche à droite, numérotées $0, 1, \dots, N - 1$ dans cet ordre.

À l'intérieur du parc, il y a $N$ personnes, également numérotées $0, 1, \dots, N - 1$. Lorsque vous annoncez une séquence $X = (X_1, X_2, \dots, X_{|X|})$ d'entiers naturels compris entre $0$ et $N - 1$, les personnes effectuent une marche selon les règles suivantes :

  1. Pour chaque $i = 0, 1, \dots, N - 1$, la personne $i$ se déplace sur la place $i$.
  2. Pour chaque $j = 1, 2, \dots, |X|$, dans cet ordre, effectuez l'opération suivante :
    • Chaque personne qui ne se trouve pas actuellement sur la place $X_j$ se déplace d'exactement une place en direction de $X_j$.

On vous donne une séquence $A = (A_0, A_1, \dots, A_{M-1})$ de longueur $M$, constituée d'entiers compris entre $0$ et $N - 1$.

Vous devez répondre à $Q$ requêtes en ligne (online). Pour chaque $i = 1, 2, \dots, Q$, des entiers $t'_i, L'_i, R'_i, P'_i$ sont donnés. Tout d'abord, reconstruisez $t_i, L_i, R_i, P_i$ à l'aide de la procédure suivante :

Soit $\text{ans}_0 = 0$, et soit $\text{ans}_i$ la réponse à la $i$-ième requête. Reconstruisez $t_i, L_i, R_i, P_i$ comme suit :

  • $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)$

Ici, pour un entier naturel $a$ et un entier strictement positif $b$, $(a \bmod b)$ désigne le reste de la division euclidienne de $a$ par $b$, compris entre $0$ et $b - 1$.

Pour chaque quadruplet reconstruit $(t_i, L_i, R_i, P_i)$, répondez à la requête suivante :

  • Si $t_i = 0$ : Soit $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulez la marche et affichez la place finale sur laquelle termine la personne $P_i$.
  • Si $t_i = 1$ : Soit $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulez la marche et affichez combien de personnes terminent sur la place $P_i$.

Entrée

L'entrée est donnée dans le format suivant :

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
  • Toutes les valeurs d'entrée sont des entiers.
  • $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$)

Sortie

Affichez $Q$ lignes. Pour chaque $i = 1, 2, \dots, Q$, affichez $\text{ans}_i$, la réponse à la $i$-ième requête.

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

2
0
3

Exemple d'entrée 2

7 4 1
3 3 3 3
1 3 0 3

Exemple de sortie 2

7

Note

Dans la première requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ avec $X = (2, 3, 2)$, la personne $2$ se déplace selon $2 \to 2 \to 3 \to 2$, donc la réponse est $2$.

Dans la deuxième requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ avec $X = (3, 2, 1)$, le nombre de personnes sur la place $3$ à la fin est $0$.

Dans la troisième requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ avec $X = (1)$, le nombre de personnes sur la place $1$ à la fin est $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.