National Olympiad in Informatics, China, 2005

Day 1, Problem 2 - Maintaining a Sequence

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

Input Format

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

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

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

Output Format

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
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

Explanation

Initially, we have the sequence:

2   -6    3    5    1   -5   -3    6    3

For the operation GET-SUM 5 4, we must find the sum of the 4 consecutive elements starting at the 5th position, as highlighted in gray below. The answer is 1 + (-5) + (-3) + 6 = -1.

2   -6    3    5    1   -5   -3    6    3

For the operation MAX-SUM, we must find the largest sum of any consecutive subsequence, as shown below. The answer is 3 + 5 + 1 + (-5) + (-3) + 6 + 3 = 10.

2   -6    3    5    1   -5   -3    6    3 

For the operation INSERT 8 3 -5 7 2, we insert the numbers -5 7 2 after the 8th number in the current sequence. The inserted numbers are highlighted in gray below.

2   -6    3    5    1   -5   -3    6   -5    7    2    3

The operation DELETE 12 1 indicates that the 12th number in the sequence must be deleted. In this case, it is the last number.

2   -6    3    5    1   -5   -3    6   -5    7    2

For the operation MAKE-SAME 3 3 2, the 3 consecutive numbers starting at the 3rd position are all changed to 2, as depicted below.

2   -6    3    5    1   -5   -3    6   -5    7    2

becomes:

2   -6    2    2    2   -5   -3    6   -5    7    2

For the operation REVERSE 3 6, we first extract the 6 consecutive elements starting with the 3rd number in the sequence:

2   -6    2    2    2   -5   -3    6   -5    7    2

Then, the extracted sequence 2 2 2 -5 -3 6, after being reversed to 6 -3 -5 2 2 2, is reinserted back into the original place:

2   -6    6   -3   -5    2    2    2   -5    7    2

For the final operations GET-SUM 5 4 and MAX-SUM, it shouldn't be hard to get the answers 1 and 10.

                  |←  GET-SUM 5 4  →|
2   -6    6   -3   -5    2    2    2   -5    7    2
                        |←         MAX-SUM        →|

Scoring

For each test case, your score will be determined as follows:

• If your program prints the correct answers to all GET-SUM operations at the correct locations in the output, then you will score 60% of points.
• If your program prints the correct answers to all MAX-SUM operations at the correct locations in the output, then you will score 40% of points.
• If your program correctly answers both types operations, then you will score 100% of points.

Please note: If your program can only correctly process one type of operation, then ensure that operations of the other type each receive a corresponding line. Otherwise, we cannot guarantee that your score will be accurate.

Constraints

You may assume that at any given time, the sequence will contain at least 1 number.
The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.

In test data worth 50% of the points, the sequence may contain up to 30 000 numbers at any given moment.
In test data worth 100% of the points, the sequence may contain up to 500 000 numbers at any given moment.

In test data worth 100% of the points, the value of any number in the sequence will be in the range [-1000, 1000].
In test data worth 100% of the points, M ≤ 20 000, the sum of all inserted values will not exceed 4 000 000, and the input will not exceed 20MB.

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 02, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The problem has cases where tot = 0 for GET-SUM. Caused me RTE a few times.