Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Det finns en park med $N$ torg placerade i en rad från vänster till höger, numrerade $0, 1, \dots, N - 1$ i denna ordning.

I parken finns det $N$ personer, också numrerade $0, 1, \dots, N - 1$. När du ropar ut en talföljd $X = (X_1, X_2, \dots, X_{|X|})$ av icke-negativa heltal mellan $0$ och $N - 1$, genomför personerna en marsch enligt följande regler:

  1. För varje $i = 0, 1, \dots, N - 1$ går person $i$ till torg $i$.
  2. För varje $j = 1, 2, \dots, |X|$, i denna ordning, gör följande:
    • Varje person som inte för tillfället befinner sig på torg $X_j$ flyttar sig exakt ett torg i riktning mot $X_j$.

Du får en talföljd $A = (A_0, A_1, \dots, A_{M-1})$ av längd $M$, bestående av heltal mellan $0$ och $N - 1$.

Du måste besvara $Q$ online-frågor. För varje $i = 1, 2, \dots, Q$ ges heltalen $t'_i, L'_i, R'_i, P'_i$. Rekonstruera först $t_i, L_i, R_i, P_i$ med följande procedur:

Låt $\text{ans}_0 = 0$, och låt $\text{ans}_i$ beteckna svaret på den $i$-te frågan. Rekonstruera $t_i, L_i, R_i, P_i$ enligt följande:

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

Här betecknar $(a \bmod b)$, för ett icke-negativt heltal $a$ och ett positivt heltal $b$, resten när $a$ delas med $b$, vilken ligger i intervallet $0$ till $b - 1$.

För varje rekonstruerad fyrpel $(t_i, L_i, R_i, P_i)$, besvara följande fråga:

  • Om $t_i = 0$: Låt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulera marschen och skriv ut det slutliga torget där person $P_i$ hamnar.
  • Om $t_i = 1$: Låt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulera marschen och skriv ut hur många personer som till slut hamnar på torg $P_i$.

Indata

Indatan ges i följande 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
  • Alla indatavärden är heltal.
  • $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$)

Utdata

Skriv ut $Q$ rader. För varje $i = 1, 2, \dots, Q$, skriv ut $\text{ans}_i$, svaret på den $i$-te frågan.

Exempel

Exempelindata 1

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

Exempelutdata 1

2
0
3

Exempelindata 2

7 4 1
3 3 3 3
1 3 0 3

Exempelutdata 2

7

Förklaring

I den första frågan i exempel 1, för $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ med $X = (2, 3, 2)$, förflyttar sig person $2$ som $2 \to 2 \to 3 \to 2$, så svaret är $2$.

I den andra frågan i exempel 1, för $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ med $X = (3, 2, 1)$, är antalet personer på torg $3$ i slutet $0$.

I den tredje frågan i exempel 1, för $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ med $X = (1)$, är antalet personer på torg $1$ i slutet $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.