3225 - Simple

Enunt

Se dă un șir de N numere și Q operații de tipul:

• 0 a b val : se va aduna valoarea val la toate numerele din intervalul [a, b].
• 1 a b : se va afișa elementul minim par și elementul maxim impar din intervalul [a, b]; în cazul în care unul dintre aceste numere nu există, se va afișa -1 în locul său.

Cerinţa

Răspundeți corect la toate operațiile de tip 1.

Date de intrare

Programul citește de la tastatură numărul N. Pe a doua linie se vor afla N numere reprezentând elementele din sir. Pe linia a treia se va afla numărul Q, iar pe următoarele Q linii se vor afla Q operații sub forma descrisa în enunț.

Date de ieșire

Se vor afișa pe ecran răspunsurile la operațiile de tip 1, câte unul pe linie.

Restricţii şi precizări

• N, Q <= 200.000
• Numerele din sir sunt cuprinse intre 1 și 2.000.000.000.
• Valorile val din operațiile de tip 0 sunt cuprinse intre 1 și 2.000.000.000.
• ATENȚIE! În cazul în care unul din cele două răspunsuri la o operație de tip 1 nu poate fi calculat, se va afișa -1

Exemplu

Intrare

7
5 6 3 1 9 8 5
10
1 2 5
0 2 3 2
1 2 4
0 2 7 3
1 2 4
1 4 7
0 5 7 1
1 1 6
1 1 2
1 3 4

Ieșire

6 9
8 5
4 11
4 11
4 13
-1 11
4 -1

Explicație

Șirul inițial este: 5 6 3 1 9 8 5. Operația 1 2 5: Se vor afișa cele doua valori cerute pe intervalul [2; 5]. Operația 0 2 3 2: Șirul nou format va fi 5 8 5 1 9 8 5. Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4]. Operația 0 2 7 3 : Șirul nou format va fi 5 11 8 4 12 11 8. Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4]. Operația 1 4 7 : Se vor afișa cele doua valori cerute pe intervalul [4; 7]. Operația 0 5 7 1 : Șirul nou format va fi 5 11 8 4 13 12 9. Operația 1 1 6 : Se vor afișa cele doua valori cerute pe intervalul [1; 6]. Operația 1 1 2 : Se vor afișa cele doua valori cerute pe intervalul [1; 2]. Operația 1 3 4 : Se vor afișa cele doua valori cerute pe intervalul [3; 4].

Rezolvare

<syntaxhighlight lang="python" line> def apply_operation_0(arr, a, b, val):

   for i in range(a - 1, b):
       arr[i] += val

def find_min_par_and_max_odd(arr, a, b):

   min_par = float('inf')
   max_odd = float('-inf')
   for i in range(a - 1, b):
       if arr[i] % 2 == 0:
           min_par = min(min_par, arr[i])
       else:
           max_odd = max(max_odd, arr[i])
   if min_par == float('inf'):
       min_par = -1
   if max_odd == float('-inf'):
       max_odd = -1
   return min_par, max_odd

def main():

   N = int(input())
   arr = list(map(int, input().split()))
   Q = int(input())

   for _ in range(Q):
       query = input().split()
       op = int(query[0])
       a = int(query[1])
       b = int(query[2])

       if op == 0:
           val = int(query[3])
           apply_operation_0(arr, a, b, val)
       elif op == 1:
           min_par, max_odd = find_min_par_and_max_odd(arr, a, b)
           print(min_par, max_odd)

if __name__ == "__main__":

   main()

</syntaxhighlight>