Editing 1901 - Median Heaps

== Cerința ==
Se dă un vector de N numere naturale nenule, indexat de la 1.
<br>
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
<br>
== Exemplul 2 ==
; Intare
: 5
: 1 2 3 4 5
: 2
: 1 4
: 3 5
; Ieșire
: 9
: 6
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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")

</syntaxhighlight>

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