Estatal 21-22 D2-P2-N02: Deseos


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Allowed languages
C, C++

(Examen clasificatorio de la Olimpiada de Informática CDMX-EDOMEX ciclo 21-22 Nivel 02 Día 2 Problema 2)

Descripción

Nati tiene una pulsera formada de cuentas, cada cuenta posee un número positivo o negativo como se muestra en la figura.

Nati toma una cuenta y empieza a sumar en el sentido de las manecillas de un reloj si durante la suma de las cuentas se obtiene un resultado negativo o la suma total también es negativa, se considera como una Maldición, pero si nunca se obtiene un valor negativo se considera como un deseo.

Ejemplo de una maldición.- Iniciando en la cuenta cuyo valor 1 se tiene que al sumar en el sentido de las manecillas del reloj 1+ (-3) = -2 se obtuvo un número negativo y por tanto representa una maldición.

Ejemplo de un deseo.- Iniciando en la cuenta cuyo valor es 3 se tiene: 3+1+(-3)+4+(-5) que equivale a 3 + 1 -3 + 4 -1, si vamos sumando cada cuenta veremos el siguiente detalle.

Observando que tanto el resultado final como los intermedios nunca fueron negativos, por tanto se tiene un deseo.

Problema

Tu tarea es construir un programa que dada una pulsera muestre cuantos deseos y maldiciones posee.

Entrada

En la primera línea un valor entero n (1\le n \le 100,000) la cantidad de cuentas en la pulsera.
En la siguiente línea habrá n números enteros llamados V_i (-100,000 \le Vi \le 100,000) indicado el valor de cada cuenta.

Salida

Dos números enteros, la cantidad de deseos y la cantidad de maldiciones que posee la pulsera.

Ejemplo

Entrada
5
3 1 -3 4 -1
Salida
2 3

Explicación.- Los dos deseos se forma iniciando en la cuenta con valor 3 (3+1-3+4-1) y en la cuenta con valor 4 (4-1+3-3). Las 3 maldiciones se localizan iniciando en las cuentas cuyos valores son 1 (ya que 1-3=-2), -1 y -3.

Subtareas

Subtarea 1 con un valor de 5 puntos.
Todas las cuentas son valores positivos o negativos y el valor de cada cuenta en el rango de -100 a 100.
Subtarea 2 con un valor de 15 puntos.
(1\le n \le2) y el valor de cada cuenta en el rango de -100 a 100.
Subtarea 3 con un valor de 20 puntos.
Solo existe una cuenta negativa y el valor de cada cuenta en el rango de -100 a 100. Subtarea 4 con un valor de 25 puntos.
(1\le n \le100) y el valor de cada cuenta en el rango de -100 a 100. Subtarea 5 con un valor de 35 puntos.
(1\le n \le100,000) el valor de cada cuenta en el rango de -100,000 a 100,000.

NOTA:

Cada subtarea contiene un conjunto de casos de prueba, se te darán los puntos siempre y cuando tu programa resuelva todos los casos de la subtarea.


Comments


  • 0
    Yosbany_ossoby  commented on Sept. 14, 2022, 1:37 a.m.

    Alguien me puede decir si se necesita algun algoritmo especifico como segment tree para resolver este problema?