DMPG '17 G2 - Holy Grail War - DMOJ: Modern Online Judge

DMPG '17 G2 - Holy Grail War

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

k_53P, Kirito

Problem type

Arthuria is preparing to fight Gilgamesh for the Holy Grail! Unfortunately, Gilgamesh activates his Noble Phantasm, Gate of Babylon, and summons $N$ ~N~ swords, and the $i^{th}$ ~i^{th}~ has destructive power $d_i$ ~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$ ~Q~ queries of two possible forms:

S i x: Gilgamesh swaps out the $i^{th}$ ~i^{th}~ sword for one of destructive value $x$ ~x~.
Q l r: Arthuria simulates destroying the contiguous subsequence with the maximum sum in the range $[l, r]$ ~[l, r]~ containing at least $1$ ~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$ ~1~: Two space separated integers, $N$ ~N~ and $Q$ ~Q~.
Line $2$ ~2~: $N$ ~N~ space separated integers, $d_i$ ~d_i~, the destructive power of Gilgamesh's original $N$ ~N~ swords.
Lines $3 \dots Q+2$ ~3 \dots Q+2~: $Q$ ~Q~ valid queries.

Output Specification

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

Constraints

For all subtasks:

$1 \le i \le N$ ~1 \le i \le N~

$1 \le l \le r \le N$ ~1 \le l \le r \le N~

Subtask 1 [5%]

$1 \le N, Q \le 100$ ~1 \le N, Q \le 100~

$-10^9 \le d_i \le 10^9$ ~-10^9 \le d_i \le 10^9~

Subtask 2 [5%]

$1 \le N, Q \le 10^5$ ~1 \le N, Q \le 10^5~

$1 \le d_i \le 10^9$ ~1 \le d_i \le 10^9~

Subtask 3 [30%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$1 \le Q \le 10^5$ ~1 \le Q \le 10^5~

$-10^9 \le d_i \le 10^9$ ~-10^9 \le d_i \le 10^9~

All $Q$ ~Q~ queries will be of the form Q l r.

Subtask 4 [60%]

$1 \le N, Q \le 10^5$ ~1 \le N, Q \le 10^5~

$-10^9 \le d_i \le 10^9$ ~-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

Comments

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)$ ~\mathcal O(N)~ copy).

19

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.

https://dmoj.ca/src/867148

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.

5

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

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

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.

No

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

5

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

Thank you.