Editorial for Marathon


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Do you know how to implement a prefix sum array? Halfway through making this question, we realized this is almost identical to a past DMOPC problem called Deforestation. So, if you finished that problem, you should've been able to do this as well. The naive solution would be to sum up the ratings between episode a and episode b and subtract that from the total rating each time. This unfortunately takes \mathcal{O}(N) time per query, and \mathcal{O}(N^2) total, which will not pass all the test cases.

To get full marks, we need a way to solve queries in \mathcal{O}(1) time. This is where the intuitive-ity of the prefix sum array comes to play. The ith element of our prefix sum array will hold the sum of all ratings from episodes 1 to episode i. This prefix sum array can be computed in \mathcal{O}(N) time. Now, how do we use this array to our advantage? The sum between two integers (a < b) is just psum[b] - psum[a-1]! Why is this? psum[b] holds k_1 + k_2 + \dots + k_b. psum[a-1] holds k_1 + k_2 + \dots + k_{a-1}. Therefore, if you take psum[b] - psum[a-1], you will be left with k_a + k_{a+1} + \dots + k_b. You should do a few cases by hand, to understand it better. Once you get the range sum, subtract it from the total rating to get the answer to your query. Since you only need 2 operations per query, the time complexity is \mathcal{O}(1), and your total complexity has been reduced to \mathcal{O}(N). Despite the difficult concept, the code is quite simple.

import sys
raw_input = sys.stdin.readline ## DONT FORGET THIS PYTHON IS SUPER SLOW
n,q = map(int,raw_input().split())
prefixsum = [0]+map(int,raw_input().split())
for i in xrange(1,n+1):
    prefixsum[i] += prefixsum[i-1]
tot = prefixsum[-1]
for i in xrange(q):
    a,b = map(int,raw_input().split())
    print tot - prefixsum[b] + prefixsum[a-1]

Comments

There are no comments at the moment.