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

<syntaxhighlight lang="python" line>

1. 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.
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.