DMPG '17 G2 - Holy Grail War - Olympiads 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^{t h}$ 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^{t h}$ 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 \leq i \leq N$

$1 \le l \le r \le N$ $1 \leq l \leq r \leq N$

Subtask 1 [5%]

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

$-10^9 \le d_i \le 10^9$ $- 10^{9} \leq d_{i} \leq 10^{9}$

Subtask 2 [5%]

$1 \le N, Q \le 10^5$ $1 \leq N, Q \leq 10^{5}$

$1 \le d_i \le 10^9$ $1 \leq d_{i} \leq 10^{9}$

Subtask 3 [30%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

$1 \le Q \le 10^5$ $1 \leq Q \leq 10^{5}$

$-10^9 \le d_i \le 10^9$ $- 10^{9} \leq d_{i} \leq 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 \leq N, Q \leq 10^{5}$

$-10^9 \le d_i \le 10^9$ $- 10^{9} \leq d_{i} \leq 10^{9}$

Sample Input

Copy

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

Sample Output

Copy

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)$ $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.