Consultas en un arreglo


Submit solution

Points: 100 (partial)
Time limit: 10.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

El próximo examen de matemáticas será muy difícil porque será una prueba contra reloj. Cada estudiante recibe un arreglo con N elementos en los cuales deberá realizar 3 posibles operaciones.

  1. update(i, x): remplaza el valor de la posición i en el arreglo por el valor de x (1 \le x \le 2000000).
  2. count(a, b): determina el número de números primos en el interval [a, b], (1 \le a \le b \le N).
  3. find(a, b): determina el mayor número no primo en el intervalo [a, b], (1 \le a \le b \le N).

Un número es primo si es mayor que 1 y solo puede dividirse entre 1 y el mismo. Escriba un programa para ejecutar Q operaciones del tipo 1, 2, y 3.

Entrada

La primera línea de la entrada contiene dos enteros (1 \le N, Q \le 100000) que representan el tamaño de la matriz y el número de operaciones a realizar, respectivamente. La segunda línea contiene N elementos separados por un espacio que representa los elementos de la matriz original. Las siguientes Q líneas representan las operaciones a realizar. Cada operación comienza con un número entero (1, 2, 3) que representa el tipo de operación, de acuerdo con lo explicado anteriormente, y en la misma línea los parámetros necesarios para ejecutar esa operación.

Salida

Para cada operación de tipo 2 o 3, imprima la respuesta en una sola línea. Si, al responder una pregunta de tipo 3, no hay un número no primo durante el intervalo [a, b], la respuesta será "NO ANSWER" sin las comillas.

Ejemplo de entrada

20 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 1 20
3 1 20
2 16 19
3 2 3
2 1 5
1 20 7
3 10 20
3 1 1

Ejemplo de salida

8
20
2
NO ANSWER
3
18
1

Comments


  • 1
    legion06  commented on Aug. 10, 2023, 6:57 p.m.

    arreglaron el problema


  • 4
    Ahmed05  commented on Aug. 6, 2023, 3:26 p.m.

    Los casos de prueba no concuerdan con las constraints del problema. En algunos casos los valores a y b de las querys tienen valor 0. Por favor arreglar este problema.