## DMPG '17 G2 - Holy Grail War

View as PDF

Points: 17 (partial)
Time limit: 1.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 containing at least 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 : 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.

#### Constraints

All queries will be of the form Q l r.

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

#### Sample Output

7

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

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

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

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

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

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

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

Brute force passes. Please raise the limits if possible.

https://dmoj.ca/src/867148

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

• commented on Oct. 13, 2018, 1:36 a.m.

insignificant's brute force solution still passes without a problem.

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

Another brute force solution just passed...

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

Is the empty sub-array an acceptable answer?

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

No

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

• commented on April 14, 2018, 4:44 p.m.

Thank you.