Another Contest 3 Problem 4 - Range Updates and Range Queries

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem types

You have an array of integers, initialized all to zero to begin with. Support two operations.

INCREMENT l r a - For each index between and , increase the th element of the array by .

SUM l r - Compute the sum of the integers between indices and , inclusive.

Constraints    Input Specification

The first line contains two positive integers, and .

The next lines each contain a sequence of positive integers. If the first integer in the line is , then three integers follow, , , and , indicating an INCREMENT operation.

Otherwise, the first integer in the line is , and then two integers follow, and , indicating a SUM operation.

Output Specification

For each SUM operation, output on its own line the result of the query. The data will be set such that this fits in a signed 32-bit integer.

3 4
1 2 3 2
2 1 1
2 2 2
2 3 3

Sample Output

0
2
4

• commented on Sept. 22, 2021, 10:14 p.m. edited

fastest time B)

Edit: man

• commented on March 22, 2021, 10:47 a.m.

I am assuming the array starts at index 0?

• commented on March 22, 2021, 10:57 a.m. so no, the array starts at index 1.

• commented on Feb. 6, 2020, 6:51 p.m.

Can anyone tell me why I'm TLEing on testcase 5? I know there's some sort of optimization but I don't know the specifics.

• commented on Feb. 7, 2020, 8:08 p.m.

Your time complexity is currently , which is insufficient given the constraints (this is on the order of operations, give or take). If you are stumped, you can try reading the tutorial :)).