DMPG '17 G2 - Holy Grail War

View as PDF

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 swords, and the has destructive power . Luckily for Arthuria, her Noble Phantasm, Excalibur, is capable of destroying any contiguous subsequence of Gilgamesh's swords. As such, Arthuria gives you queries of two possible forms:

1. S i x: Gilgamesh swaps out the sword for one of destructive value .
2. Q l r: Arthuria simulates destroying the contiguous subsequence with the maximum sum in the range . 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 : Two space separated integers, and .
Line : space separated integers, , the destructive power of Gilgamesh's original swords.
Lines : valid queries.

Output Specification

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

For all subtasks, , and .

Subtaks 2 [5 points]

All queries will be of the form Q l r.

Sample Input

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

Sample Output

7

• 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

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

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

Another brute force solution just passed...

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

Is the empty sub-array an acceptable answer?

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

No

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