DMPG '17 G2 - Holy Grail War

View as PDF

Submit solution


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

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

Subtasks

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

Comments


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

    Brute force passes. Please raise the limits if possible.

    https://dmoj.ca/src/867148


    • 1
      ss__jonathan  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.


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

      Another brute force solution just passed...


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

    Is the empty sub-array an acceptable answer?


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

      No

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