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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
This problem is almost template PSA (Prefix Sum Array). The initial array is just preprocessed such that each even-numbered house has a negative .
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