Fişierul intrare/ieşire:vmin.in, vmin.outSursăFMI No Stress 2012
AutorAdrian Budau, Serban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vmin

Se dau N functii liniare de forma A * T + B. Sa se determine pentru M query-uri, care este functia de valoare minima la un moment oarecare T. Query-urile se dau in ordine crescatoare dupa T.

Date de intrare

Fişierul de intrare vmin.in va contine pe prima linie doua numere naturale N si M. Pe urmatoarele N linii se vor gasi N perechi de numere intregi, reprezentand valorile A si B pentru fiecare functie. Pe linia N+2 se vor gasi M elemente, reprezentand momentele de timp pentru care trebuie sa determinam functia de valoare minima.

Date de ieşire

În fişierul de ieşire vmin.out se vor gasi pe o singura linie M valori, reprezentand raspunsurile la cele M query-uri. Raspunsul la un query este reprezentat de indicele functiei de valoare minima la acel moment.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 1 000 000
  • -109A,B ≤ 109
  • 0 ≤ T ≤ 109
  • Pentru teste in valoare de 40p, N ≤ 1000, M ≤ 3000

Exemplu

vmin.invmin.out
4 3
4 5
2 9
8 7
11 3
0 5 7
4 2 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content