Maintaining a Sequence

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 3.0s

Memory limit: 256M

Author:

Ninjaclasher

Problem type

Please write a program that maintains a sequence, supporting the following operations:

Operation	Input Format	Description
1. Modify	`MAKE-SAME posi tot c`	Starting at the $posi$ ~posi~-th number in the current sequence, change all the values of $tot$ ~tot~ consecutive numbers to $c$ ~c~.
2. Get Sum	`GET-SUM posi tot`	Starting at the $posi$ ~posi~-th number in the current sequence, output the sum of $tot$ ~tot~ consecutive numbers.
3. Max Sum	`MAX-SUM`	Output the largest sum of any (non-empty) consecutive subsequence of the current sequence.

Input Specification

The first line of input contains two integers $N$ ~N~ and $M$ ~M~, where $N$ ~N~ is the initial length of the sequence and $M$ ~M~ is the number of operations.

The second line of input contains $N$ ~N~ integers, describing the initial sequence.

For the next $M$ ~M~ lines, each line will contain a command in one of the formats described above.

Output Specification

For each GET-SUM or MAX-SUM operation in the input, output the result of the query on a separate line.

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
MAKE-SAME 3 3 2
GET-SUM 5 4
MAX-SUM
MAKE-SAME 2 1 12
MAX-SUM
GET-SUM 8 2

Sample Output

Constraints

The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.

In test data worth $40\%$ ~40\%~ of the points, $N \le 100$ ~N \le 100~.
In test data worth $100\%$ ~100\%~ of the points, $N \le 100$ ~N \le 100~ $000$ ~000~.

In test data worth $100\%$ ~100\%~ of the points, the value of any number in the sequence will be in the range $[-10$ ~[-10~ $000, 10$ ~000, 10~ $000]$ ~000]~.
In test data worth $100\%$ ~100\%~ of the points, $M \le 100$ ~M \le 100~ $000$ ~000~.

Comments

0

mastery commented on Nov. 30, 2018, 6:42 p.m.

definitely not Holy Grail War

0

_ commented on June 16, 2019, 9:54 p.m.

definitely not as cheesable as holy grail war