DMPG '17 G2 - Holy Grail War

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Arthuria is preparing to fight Gilgamesh for the Holy Grail! Unfortunately, Gilgamesh activates his Noble Phantasm, Gate of Babylon, and summons N swords, and the i^{th} has destructive power d_i. Luckily for Arthuria, her Noble Phantasm, Excalibur, is capable of destroying any contiguous subsequence of Gilgamesh's swords. As such, Arthuria gives you Q queries of two possible forms:

  1. S i x: Gilgamesh swaps out the i^{th} sword for one of destructive value x.
  2. Q l r: Arthuria simulates destroying the contiguous subsequence with the maximum sum in the range [l, r]. Note that she does not actually destroy these swords.

As Arthuria's master, you wish to know the answer to all of the queries of the form Q l r. Help win the Holy Grail!

Input Specification

Line 1: Two space separated integers, N and Q.
Line 2: N space separated integers, d_i, the destructive power of Gilgamesh's original N swords.
Lines 3 \ldots Q + 2: Q valid queries.

Output Specification

Print the answer to each query of the form Q l r.


For all subtasks, 1 \le i \le N, and 1 \le l \le r \le N.

Subtask 1 [5 points]

1 \le N \le 100
1 \le Q \le 100
-10^9 \le d_i \le 10^9

Subtaks 2 [5 points]

1 \le N \le 10^5
1 \le Q \le 10^5
1 \le d_i \le 10^9

Subtask 3 [30 points]

1 \le N \le 1000
1 \le Q \le 10^5
-10^9 \le d_i \le 10^9

All Q queries will be of the form Q l r.

Subtask 4 [60 points]

1 \le N \le 10^5
1 \le Q \le 10^5
-10^9 \le d_i \le 10^9

Sample Input

8 2
1 2 3 4 5 6 7 8
S 1 2
Q 1 3

Sample Output



  • 7
    Plasmatic  commented on Feb. 27, 2019, 11:12 p.m.

    It's never mentioned that for the Q operation, at least one sword must be destroyed (even if it is better to not destroy any swords)

  • 6
    insignificant  commented on April 14, 2018, 1:36 p.m. edited

    Brute force passes. Please raise the limits if possible.

    • 4
      Rimuru  commented on Oct. 12, 2018, 5:08 p.m.

      Time limit for this question has been lowered, and AC submissions that were not intended (specifically brute force) have been rejudged.

    • 5
      eric574  commented on Sept. 22, 2018, 6:17 p.m.

      Another brute force solution just passed...

  • 6
    insignificant  commented on April 14, 2018, 12:06 p.m.

    Is the empty sub-array an acceptable answer?

    • 8
      wleung_bvg  commented on April 14, 2018, 12:42 p.m.


      (well at least it doesn't pass the test cases...)