infiniterace
Day1 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Spanish (ESP)

A. Carrera inﬁnita
Nombre del problema

Carrera Inﬁnita

Límite de Tiempo

1 segundo

Límite de Memoria

1 gigabyte

Cada año, una maratón tiene lugar en Eindhoven. Este año, los organizadores han pensado en
hacer algo especial y, en lugar de acabar tras los 42 kilómetros, ¡la carrera dura para siempre! Para
simpliﬁcar la organización, la carrera se realiza en un circuito de atletismo de la universidad deEindhoven, y los participantes corren un número inﬁnito de vueltas en el cicuito.
Anika está muy emocionada de ser una de las N participantes, numeradas desde 0 hasta N − 1.
Fue muy rápida en apuntarse, lo que signiﬁca que es la participante número 0. Anika empiezajusto tras la línea de salida, con todas las otras participantes posicionadas delante de ella en elcircuito. Anika no es capaz de recordar cuantas vueltas ha recorrido, pero recuerda cuándo
adelanta a alguien o alguien la adelanta. ¿Cuál es el mínimo número de veces que debe de habercruzado la línea de ﬁnal del circuito? Nadie se desplaza hacia atrás, y ningún adelantamiento
sucede exactamente en la línea de ﬁnal. Además, observad que las participantes nonecesariamente corren a velocidad constante.

EntradaLa primera línea de la entrada contiene un entero N , el número de participantes.
La segunda línea contiene un entero Q, el número de acontecimientos.

infiniterace (1 of 4)

Las siguientes Q líneas describen los eventos en el orden en que ocurren durante la carrera. La i ésima línea contiene un entero xi .
Si xi > 0, eso signiﬁca que Anika ha adelantado la participante xi .
Si xi < 0, eso signiﬁca que la participante −xi ha adelantado a Anika.

SalidaDebes imprimir un único entero, el mínimo número de veces que Anika debe de haber cruzado lalínea de ﬁnal del circuito.

Restricciones y Puntuación
2 ≤ N ≤ 200 000.
1 ≤ Q ≤ 200 000.
1 ≤ xi ≤ N − 1 o −(N − 1) ≤ xi ≤ −1.
Tu solución será evaluada en un conjunto de subtareas, cada una valorada en un número depuntos. Cada subtarea contendrá un número de casos de prueba. Para obtener los puntos de una
subtarea, debes resolver todos los casos de prueba en la subtarea.
Subtarea

Puntuación

Restricciones

129

N =2234xi > 0 para todo i (eso quiere decir que Anika solo adelanta)

322N , Q ≤ 100

415Sin restricciones adicionales

EjemplosObservad que algunos de los ejemplos no son válidos para todas las subtareas.
En el primer ejemplo, hay N = 4 participantes y Q = 5 acontecimientos. Anika primero esadelantada por 2, quien ahora se encuentra una vuelta entera por delante de Anika. Entonces
Anika adelanta a 2 otra vez, para seguidamente adelantar a 1 y posteriormente ser adelantada por

3. En este punto, Anika aún podría encontrarse en su primera vuelta. Finalmente, Anika adelanta a
2 otra vez, y eso implica que debe de haber cruzado la línea de ﬁnal como mínimo una vez.
En el segundo ejemplo, solo hay una participante aparte de Anika. Anika adelanta la otra
participante 4 veces, lo que signiﬁca que Anika debe de haber cruzado la línea de ﬁnal al menos
tres veces.

infiniterace (2 of 4)

Entrada

45-2
2Salida

1

1-3
2

2
4
1

3

1
1
1

2
5

0

1-1
1-1-1

20000037199999
199999119999955
19999955

infiniterace (3 of 4)

Entrada

36Salida

312
2
2
1
1

infiniterace (4 of 4)