Fişierul intrare/ieşire:turnuri2.in, turnuri2.outSursăAlgoritmiada 2011, Runda 2
AutorTiberiu SavinAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.6 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Turnuri2

In San Francisco, firmele de software, din dorinta de a isi arata puterea, si-au construit sediile sub forma unor turnuri foarte inalte si foarte frumoase. De asemenea primaria orasului a decis sa dea autorizatie de construire pentru aceste turnuri pe aceeasi strada, astfel ca toate turnurile sunt dispuse in linie. Alexandra, care tocmai a terminat facultatea de informatica, si a primit oferta de angajare la toate aceste firme, trebuie sa aleaga la care din aceste companii sa se angajeze. Ea a decis sa faca aceasta alegere in functie de privelistea pe care o are in fiecare firma la pauza de masa. Se stie ca in fiecare firma, pauza de masa se ia pe acoperis si de acolo Alexandra poate vedea toate turnurile in stanga sau in dreapta pana la primul care e strict mai inalt decat turnul pe care se afla ea, inclusiv.

Cerinta

Se da N, numarul de firme din San Francisco, iar pentru fiecare din cele N turnuri se cunoaste inaltimea lui, Hi, si coeficientul sau de frumusete, Ki. Se cere sa se spuna pentru fiecare turn in parte, care este cel mai frumos turn vizibil de pe acoperisul acestuia.

Date de intrare

Fişierul de intrare turnuri2.in va contine pe prima linie numarul N cu semnificatia din enunt. Pe urmatoarele N linii se vor afla cate doua numere, Hi si Ki, reprezentand inaltimea si coeficientul de frumusete al turnului respectiv.

Date de ieşire

În fişierul de ieşire turnuri2.out se vor afisa N linii cu semnificatia ca pe linia i se va afla coeficientul de frumusete al celui mai frumos turn vizibil de pe acoperisul turnului i.

Restricţii

  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ Hi, Ki ≤ 1 000 000 000
  • De pe acoperisul unui turn i este vizibil si turnul i

Exemplu

turnuri2.inturnuri2.out
4
3 2
5 5
6 1
4 3
5
5
5
3

Explicaţie

Primele trei turnuri vad turnul 2 care are coeficientul de frumusete 5, acesta fiind de altfel cel mai frumos turn din vale. Ultimul turn insa nu poate vedea acest turn din cauza turnului 3, coeficientul maxim de frumusete vizibil de pe acoperisul sau fiind chiar el, cu coeficientul 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content