DMPG '17 G2 - Holy Grail War

View as PDF

Submit solution

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

Problem type

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] containing at least 1 sword. 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 \dots 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

1 \le l \le r \le N

Subtask 1 [5%]

1 \le N, Q \le 100

-10^9 \le d_i \le 10^9

Subtask 2 [5%]

1 \le N, Q \le 10^5

1 \le d_i \le 10^9

Subtask 3 [30%]

1 \le N \le 1\,000

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%]

1 \le N, 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



  • 1
    dxke02  commented on March 1, 2021, 6:50 p.m.

    Any reason why changing my c++ vectors into arrays passed?

    • 2
      Dan13llljws  commented on March 1, 2021, 8:44 p.m.

      If you want to pass a vector, you can try passing the reference instead of the value.

    • 2
      Kirito  commented on March 1, 2021, 7:22 p.m.

      I suspect passing vectors by value is slow (specifically, I think it requires an \mathcal O(N) copy).

  • 18
    Plasmatic  commented on Feb. 28, 2019, 4:12 a.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)

  • 7
    insignificant  commented on April 14, 2018, 5:36 p.m. edited

    Brute force passes. Please raise the limits if possible.

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

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

    • 2
      eric574  commented on Sept. 22, 2018, 10:17 p.m.

      Another brute force solution just passed...

  • 11
    insignificant  commented on April 14, 2018, 4:06 p.m.

    Is the empty sub-array an acceptable answer?

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


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