Editorial for LCC '24 Contest 1 S1 - Graham's Candy Planning


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.

Author: Colin

This problem is almost template PSA (Prefix Sum Array). The initial array is just preprocessed such that each even-numbered house has a negative C_i.

The rest of the problem is trivial (if you know how to use a PSA). Knowing how to use a PSA is left as an exercise to the reader.

(Just kidding. Go check out https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/)

n = int(input())
*c, = map(int, input().split())

# Make the prefix sum array.
psa = [0] * (len(c) + 1)
for i, v in enumerate(c):
    psa[i + 1] = psa[i] + (v if i % 2 == 0 else -v)

# Answer the queries.
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(psa[r] - psa[l - 1])

Comments

There are no comments at the moment.