Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Puistossa on $N$ aukiota, jotka on järjestetty riviin vasemmalta oikealle ja numeroitu tässä järjestyksessä $0, 1, \dots, N - 1$.

Puistossa on $N$ henkilöä, jotka on myös numeroitu $0, 1, \dots, N - 1$. Kun ilmoitat epänegatiivisista kokonaisluvuista väliltä $0$ – $N - 1$ koostuvan jonon $X = (X_1, X_2, \dots, X_{|X|})$, henkilöt suorittavat marssin seuraavien sääntöjen mukaisesti:

  1. Jokaiselle $i = 0, 1, \dots, N - 1$, henkilö $i$ siirtyy aukiolle $i$.
  2. Jokaiselle $j = 1, 2, \dots, |X|$, tässä järjestyksessä, tehdään seuraavaa:
    • Jokainen henkilö, joka ei tällä hetkellä ole aukiolla $X_j$, siirtyy täsmälleen yhden aukion verran kohti aukiota $X_j$.

Annettuna on pituutta $M$ oleva jono $A = (A_0, A_1, \dots, A_{M-1})$, joka koostuu kokonaisluvuista väliltä $0$ – $N - 1$.

Sinun on vastattava $Q$ online-kyselyyn. Jokaiselle $i = 1, 2, \dots, Q$ annetaan kokonaisluvut $t'_i, L'_i, R'_i, P'_i$. Muodosta ensin luvut $t_i, L_i, R_i, P_i$ seuraavalla menettelyllä:

Olkoon $\text{ans}_0 = 0$, ja tarkoittakoon $\text{ans}_i$ vastausta $i$:nteen kyselyyn. Muodosta $t_i, L_i, R_i, P_i$ seuraavasti:

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

Tässä epänegatiiviselle kokonaisluvulle $a$ ja positiiviselle kokonaisluvulle $b$ merkintä $(a \bmod b)$ tarkoittaa jakojäännöstä, kun $a$ jaetaan $b$:llä, mikä on välillä $0$ – $b - 1$.

Vastaa jokaiselle muodostetulle nelikolle $(t_i, L_i, R_i, P_i)$ seuraavaan kyselyyn:

  • Jos $t_i = 0$: Olkoon $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuloi marssi ja tulosta aukio, jolle henkilö $P_i$ lopulta päätyy.
  • Jos $t_i = 1$: Olkoon $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuloi marssi ja tulosta, kuinka monta henkilöä päätyy lopulta aukiolle $P_i$.

Syöte

Syöte annetaan seuraavassa muodossa:

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
  • Kaikki syötteen arvot ovat kokonaislukuja.
  • $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$)

Tuloste

Tulosta $Q$ riviä. Jokaiselle $i = 1, 2, \dots, Q$, tulosta $\text{ans}_i$, vastaus $i$:nteen kyselyyn.

Esimerkit

Esimerkkisyöte 1

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

Esimerkkituloste 1

2
0
3

Esimerkkisyöte 2

7 4 1
3 3 3 3
1 3 0 3

Esimerkkituloste 2

7

Huomautus

Esimerkin 1 ensimmäisessä kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ ja jonolla $X = (2, 3, 2)$ henkilö $2$ liikkuu $2 \to 2 \to 3 \to 2$, joten vastaus on $2$.

Esimerkin 1 toisessa kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ ja jonolla $X = (3, 2, 1)$ aukiolla $3$ olevien henkilöiden määrä lopussa on $0$.

Esimerkin 1 kolmannessa kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ ja jonolla $X = (1)$ aukiolla $1$ olevien henkilöiden määrä lopussa on $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.