Problem K
Gladiatorer
Languages
en
sv
I romarriket var gladiatorstrider en populär sport. För att utföra en strid ställer sig $N$ gladiatorer på ett led, vars platser är numrerade från $0$ till $N-1$. Varje gladiator har en unik styrka mellan $0$ och $N-1$. Sedan kommer det ske gånger att anfall. Under ett anfall börjar någon gladiator att springa antingen höger eller vänster. Den besegrar sedan alla gladiatorer den stöter på, vars styrka är strikt mindre än den anfallandes. Om gladiatorn når radens slut, antingen till höger eller vänster, eller stöter på en starkare gladiator, så avslutar den sitt anfall och går tillbaka till platsen de stod på tidigare. Alla besegrade gladiatorer lämnar ledet, och lämnar en tom plats efter sig. Besegrade gladiatorer kan inte stoppa framtida gladiatorers anfall eller anfalla själva.
Du har nu hittat en lista av alla anfall som skedde under en viss strid. För varje besegrad gladiator vill du nu avgöra vem som besegrade den.
Indata
Den första raden i indatan innehåller heltalen $N$ och $Q$ ($1 \leq N,Q \leq 3 \cdot 10^5$), antalet gladiatorer och antalet anfall.
Därefter följer en rad med $N$ heltal $s_0, s_1, \dots , s_{N-1}$ ($0 \leq s_i \leq N-1$), gladiatorernas styrkor. Det är garanterat att för varje styrka mellan $0$ och $N-1$ finns det exakt en gladiator med den styrkan.
Sedan följer $Q$ rader som vardera innehåller heltalet $P$ och bokstaven $D$ ($0 \leq P \leq N-1$, $D \in {<,>}$), vilket beskriver positionen av en gladiator som påbörjar ett anfall och dess riktning. Dessa ges i samma ordning som attackerna sker. Det är garanterat att besegrade gladiatorer aldrig påbörjar anfall.
Utdata
Skriv ut $N$ heltal på en enda rad: för varje gladiator, skriv ut positionen av gladiatorn som besegrade den. Om en viss gladiator aldrig besegras, skriv istället ut $-1$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$15$ |
$N, Q \leq 1000$ |
|
$2$ |
$25$ |
$N \leq 5000$ |
|
$3$ |
$60$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I första anfallet besegrar gladiatorn på position $1$ gladiatorn på position $2$. Vid position $3$ stöter den på en starkare gladiator, och avslutar därmed sitt anfall.
Sedan anfaller gladitorn med styrka $4$ längst till höger. Den besegrar då alla kvarvarande gladiatorer förutom den längst till vänster. Notera att den inte besegrar gladiatorn på position $2$, eftersom denna redan är besegrad.
I sista anfallet besegrar gladiatorn med styrka $5$ på position $0$ den kvarvarande gladiatorn. Eftersom denna gladiatorn aldrig besegras, så ska du skriva ut $-1$ på position $0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 4 1 0 2 3 1 > 4 < 0 > |
-1 4 1 4 0 |
