Tres-Veltör y su Batallón


Submit solution

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

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

El joven vikingo Tres-Veltör es ahora el nuevo comandante de el batallón de infantería del Valhalla. Sus guerreros hoy están practicando unos ejercicios tácticos de modo preventivo para el Ragnarök. Sus N guerreros están ubicados en una línea recta, cada uno ocupando la posición i y con una fuerza a_i. Como todo no es coser y cantar Tres-Veltör se dio cuenta que sus guerreros estaban demasiado cerca entre ellos y si manda al guerrero i a la batalla no puede mandar a sus adyacentes (note que el primero y el último solo tienen un adyacente) ya que se harían daño entre ellos. Tres-Veltör puede mandar cualquier subconjunto de guerreros siempre que cumpla con estos requisitos incluso si este está vacío.

El batallón realizará Q ejercicios tácticos, antes de cada ejercicio un guerrero de Tres-Veltör tomará una poción mágica que cambiará su fuerza actual hasta que este tome otra poción. Su tarea es decirle a Tres-Veltör antes de cada ejercicio táctico cuál es la mayor fuerza que puede lograr su batallón.

Entrada

La primera línea contiene los enteros N y Q (1 \leq N, Q \leq 10^5), el número de guerreros de Tres-Veltör y la cantidad de ejercicios tácticos.

La segunda línea contiene N enteros separados por espacio donde el i-ésimo entero representa a a_i (-10^9 \leq a_i \leq 10^9), la fuerza del i-ésimo guerrero.

Las siguientes Q líneas contienen dos enteros pos (1 \leq pos \leq N) y val (-10^9 \leq val \leq 10^9) que significan que el guerrero con índice pos ahora tiene una fuerza igual a val (i. e. a_{pos} := val).

Salida

Q líneas donde la i-ésima línea posee un entero que representa la mayor fuerza posible del batallón luego de que el guerrero con indice pos_i tome su poción.

Subtareas

  • Subtarea 1 (5 puntos): 1 \leq N \leq 20,\ 1 \leq Q \leq 5.
  • Subtarea 2 (12 puntos): (0 \leq a_i,\ val \leq 1).
  • Subtarea 3 (13 puntos): Q = 1.
  • Subtarea 4 (20 puntos): N es una potencia de 2.
  • Subtarea 5 (40 puntos): Sin restricciones adicionales.

Ejemplo #1 de Entrada

5 9
0 0 0 0 1
1 2
2 5
3 10
4 9
2 -1
3 -3
1 -4
4 -2
5 -1

Ejemplo #1 de Salida

3
6
13
14
13
11
9
1
0

Ejemplo #2 de Entrada

5 3
1
2
3
4
5
5 2
2 7
1 10

Ejemplo #2 de Salida

6
11
15

Comments


  • -1
    hohemhein  commented on Feb. 4, 2021, 5:25 p.m.

    Bro he intentado escribirte pero no te llega ningun mensaje.Mi alias es hohemhein20 . Intenta tu a ver si llega


  • -1
    hohemhein  commented on Jan. 29, 2021, 4:39 p.m.

    Como puedo resolver este ejercicio?


    • -1
      Albe  commented on Feb. 1, 2021, 10:11 p.m.

      Si tienes telegram puedes escribirme y puedo explicarte por privado, mi alias es @albertolg101