Fişierul intrare/ieşire:cartita.in, cartita.outSursăOSEPI 2021 baraj gimnaziu
AutorDana LicaAdăugată demircea_007Mircea Rebengiuc mircea_007
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Cârtița (baraj gimnaziu)

În grădina lui Macarie există un şir de N morcovi, numerotaţi de la 1 la N. Ca să ştie unde sunt plantaţi, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov şi a notat înălţimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălţimea de h[i] centimetri. O cârtiţă neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie către un morcov, tot pământul rezultat îl scoate afară modificând astfel înălţimea grămăjoarei corespunzătoare acelui morcov, dar şi ale celorlalţi morcovi din grădină. Dacă, în urma săpării unei galerii către morcovul de pe poziţia pos, înălţimea grămăjoarei lui a crescut cu x centimetri atunci înălţimile grămăjoarelor tuturor morcovilor se modifică după următoarea regulă ce depinde de un număr K:

  • înălţimea grămăjoarei morcovului pos − 1 se modifică cu x − K centimetri iar a morcovului pos + 1 cu x + K centimetri,
  • înălţimile gramăjoarelor morcovilor pos − 2 şi pos + 2 se modifică cu x − 2 · K respectiv x + 2 · K centimetri
  • În caz general, înălţimea se modifică după următoarele reguli pentru fiecare morcov din grădină:
    • Înălţimea h[pos − i] devine h[pos − i] + x − i · K, pentru fiecare i, 1 ≤ i ≤ pos − 1
    • Înălţimea h[pos + i] devine h[pos + i] + x + i · K, pentru fiecare i, 1 ≤ i ≤ N − pos

Cerinţă

Se cunosc înălţimile iniţiale ale tuturor celor N grămăjoare şi cele U modificări făcute de cârtiţă asupra înălţimilor grămăjoarelor de pământ ale morcovilor.
Ştim că în cadrul unei secvenţe continue de morcovi cel mai tentant pentru cârtiţă este morcovul cu cea mai mică înălţime a grămăjoarei de pământ.
Ajutaţi-l pe Macarie să identifice înălţimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiţă.

Date de intrare

Fişierul de intrare cartita.in conţine pe prima linie un număr natural N având semnificaţia din enunţ. Pe următoarea linie se află N numere naturale despărţite prin câte un spaţiu reprezentând, în ordine, înălţimile grămăjoarelor de pământ, al i-lea număr reprezentând înălţimea iniţială h[i] a grămăjoarei din dreptul morcovului i. Pe a treia linie se află un număr natural U reprezentând numărul de morcovi către care cărtiţa a săpat galerii. Pe următoarele U linii se află câte un triplet de numere naturale pos, x, K, separate între ele prin câte un spaţiu, cu semnificaţia că, în urma săpării unei galerii către morcovul pos, înălţimea grămăjoarei lui a crescut cu x centimetri iar celelalte înălţimi se modifică după regula descrisă în enunţ. Pe următoarea linie se găseşte numărul Q reprezentând numărul de intervale unde se doreşte identificarea înălţimii minime a unei grămăjoare corespunzătoare celui mai tentant morcov. Pe următoarele Q linii sunt câte două numere naturale L, R, separate între ele printr-un spaţiu, reprezentând capetele intervalului de morcovi investigat.

Date de ieşire

Fişierul de ieşire cartita.out va conţine Q linii pe fiecare găsindu-se, în ordine, răspunsul la intervalele investigate.

Restricţii şi precizări

  • 1 ≤ N ≤ 100 000
  • 1 ≤ U ≤ 300 000
  • 1 ≤ Q ≤ 200 000
  • 1 ≤ LRN
  • Iniţial 1 ≤ h[i] ≤ N, pentru fiecare i, 1 ≤ i ≤ N
  • 1 ≤ pos ≤ N , 1 ≤ x ≤ 400 şi −21 ≤ K ≤ 21, K ≠ 0
  • Subtask 1 – 12 puncte: N, U, Q ≤ 2 000
  • Subtask 2 – 9 puncte: N, U ≤ 2 000 şi Q ≤ 200 000
  • Subtask 3 – 25 de puncte: N, U ≤ 75 000 şi Q ≤ 15
  • Subtask 4 – 17 puncte: N, U, Q ≤ 75 000
  • Subtask 5 – 16 puncte: N ≤ 100 000, U ≤ 300 000 şi Q ≤ 15
  • Subtask 6 – 7 puncte: N ≤ 100 000, U ≤ 300 000 şi Q ≤ 10 000
  • Subtask 7 – 14 puncte: Nu există restricţii suplimentare.

Exemplu

cartita.incartita.out
6
1 6 2 4 3 4
3
4 5 2
2 4 1
4 2 8
3
1 6
2 4
4 4
-19
-3
17

Explicaţie

  • După prima galerie săpată către morcovul 4, şirul înălţimilor celor N = 6 grămăjoare a devenit (0, 7, 5, 9, 10, 13).
  • După a doua galerie săpată către morcovul 2, şirul înălţimilor celor N = 6 grămăjoare a devenit (3, 11, 10, 15, 17, 21).
  • După a treia galerie săpată către morcovul 4, şirul înălţimilor celor N = 6 grămăjoare a devenit (−19, −3, 4, 17, 27, 39)
  • Pe intervalul [1, 6], înălţimea minimă este −19, pe intervalul [2, 4], înălţimea minimă este −3, iar pentru ultimul interval investigat [4, 4] înălţimea minimă este 17.
Trebuie sa te autentifici pentru a trimite solutii. Click aici