Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Es gibt einen Park mit $N$ Plätzen, die in einer Reihe von links nach rechts angeordnet und in dieser Reihenfolge mit $0, 1, \dots, N - 1$ nummeriert sind.

Im Park befinden sich $N$ Personen, die ebenfalls mit $0, 1, \dots, N - 1$ nummeriert sind. Wenn du eine Folge $X = (X_1, X_2, \dots, X_{|X|})$ aus nichtnegativen ganzen Zahlen zwischen $0$ und $N - 1$ bekanntgibst, führen die Personen einen Marsch nach den folgenden Regeln durch:

  1. Für jedes $i = 0, 1, \dots, N - 1$ begibt sich Person $i$ auf Platz $i$.
  2. Für jedes $j = 1, 2, \dots, |X|$ wird in dieser Reihenfolge Folgendes ausgeführt:
    • Jede Person, die sich derzeit nicht auf Platz $X_j$ befindet, bewegt sich genau einen Platz in Richtung $X_j$.

Gegeben ist eine Folge $A = (A_0, A_1, \dots, A_{M-1})$ der Länge $M$, die aus ganzen Zahlen zwischen $0$ und $N - 1$ besteht.

Du musst $Q$ Online-Anfragen beantworten. Für jedes $i = 1, 2, \dots, Q$ sind ganze Zahlen $t'_i, L'_i, R'_i, P'_i$ gegeben. Rekonstruiere zunächst $t_i, L_i, R_i, P_i$ mit dem folgenden Verfahren:

Sei $\text{ans}_0 = 0$, und sei $\text{ans}_i$ die Antwort auf die $i$-te Anfrage. Rekonstruiere $t_i, L_i, R_i, P_i$ wie folgt:

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

Hierbei bezeichnet $(a \bmod b)$ für eine nichtnegative ganze Zahl $a$ und eine positive ganze Zahl $b$ den Rest bei der Division von $a$ durch $b$, der im Bereich von $0$ bis $b - 1$ liegt.

Beantworte für jedes rekonstruierte Tupel $(t_i, L_i, R_i, P_i)$ die folgende Anfrage:

  • Wenn $t_i = 0$: Sei $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuliere den Marsch und gib den Platz aus, auf dem Person $P_i$ am Ende landet.
  • Wenn $t_i = 1$: Sei $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuliere den Marsch und gib aus, wie viele Personen am Ende auf Platz $P_i$ landen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

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
  • Alle Eingabewerte sind ganze Zahlen.
  • $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$)

Ausgabe

Gib $Q$ Zeilen aus. Gib für jedes $i = 1, 2, \dots, Q$ den Wert $\text{ans}_i$ aus, die Antwort auf die $i$-te Anfrage.

Beispiele

Beispieleingabe 1

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

Beispielausgabe 1

2
0
3

Beispieleingabe 2

7 4 1
3 3 3 3
1 3 0 3

Beispielausgabe 2

7

Hinweis

In der ersten Anfrage von Beispiel 1 bewegt sich für $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ mit $X = (2, 3, 2)$ die Person $2$ gemäß $2 \to 2 \to 3 \to 2$, also lautet die Antwort $2$.

In der zweiten Anfrage von Beispiel 1 beträgt für $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ mit $X = (3, 2, 1)$ die Anzahl der Personen auf Platz $3$ am Ende $0$.

In der dritten Anfrage von Beispiel 1 beträgt für $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ mit $X = (1)$ die Anzahl der Personen auf Platz $1$ am Ende $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.