1901 - Median Heaps

Cerința

Se dă un vector de N numere naturale nenule, indexat de la 1.
Se cere să se raspundă la Q interogări de tipul:

• pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.

Într-un interval [l, r], puteți crește sau micșora fiecare element cu costul x unde x este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri.

Date de intrare

• pe prima linie numărul N.
• pe a doua linie N numere naturale nenule : x1 ,x2 , … xN.
• pe a treia linie numărul Q.
• pe următoarele Q linii 2 numere: l, r.

Date de ieșire

Se vor afișa Q numere pe fiecare linie, reprezentând constul total minim, al fiecărui interval l r.

Restricții și precizări

• 1 ≤ N, Q ≤ 100.000
• 1 ≤ l ≤ r ≤ 100.000
• 1 ≤ xi ≤ 1.000.000.000

Exemplul 1

Intrare

9

3 2 16 15 12 6 20 4 5

3

2 7

2 2

3 8

Ieșire

31

0

29

Exemplul 2

Intare

5

1 2 3 4 5

2

1 4

3 5

Ieșire

9

6

Rezolvare

#1901 - Median Heaps
def is_valid_input(N, Q, x_values, queries):
    if not (1 <= N <= 100000 and 1 <= Q <= 100000):
        return False
    if not all(1 <= xi <= 1000000000 for xi in x_values):
        return False
    if not all(1 <= l <= r <= N for l, r in queries):
        return False
    return True


def minimize_costs(N, x_values, Q, queries):
    result = []
    for l, r in queries:
        interval = x_values[l - 1:r]
        min_value = min(interval)
        cost = sum(min_value - xi for xi in interval)
        result.append(cost)
    return result


if __name__ == "__main__":
    try:
        # Citire date de intrare
        N = int(input())
        x_values = list(map(int, input().split()))
        Q = int(input())
        queries = [tuple(map(int, input().split())) for _ in range(Q)]

        # Verificare restricții
        if not is_valid_input(N, Q, x_values, queries):
            print("Fals")
        else:
            # Calcul și afișare rezultate
            results = minimize_costs(N, x_values, Q, queries)
            for result in results:
                print(result)

    except ValueError:
        print("Fals")

 Explicatie 

Pentru intervalul [2, 7], costul total minim este 31, deoarece egalizăm fiecare număr din interval cu 12.
Pentru intervalul [2, 2], costul total minim este 0, deoarece avem un singur element în interval.
Pentru intervalul [3, 8], costul total minim este 29, deoarece egalizăm fiecare număr din interval cu 12.