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

##### Subtask 3 [30%]

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

• commented on March 4, 2021, 9:59 p.m. edit 3

Bruh. had to replace one letter. D:

ig i dont need help anymore. smashes keyboard

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

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

• commented on March 1, 2021, 3: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, 2:22 p.m.

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

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

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

Brute force passes. Please raise the limits if possible.

https://dmoj.ca/src/867148

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

• commented on Oct. 12, 2018, 9:36 p.m.

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

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

Another brute force solution just passed...

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

Is the empty sub-array an acceptable answer?

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

No

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

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

Thank you.