| Fişierul intrare/ieşire: | vmin.in, vmin.out | Sursă | FMI No Stress 2012 |
| Autor | Adrian Budau, Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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
- -109 ≤ A,B ≤ 109
- 0 ≤ T ≤ 109
- Pentru teste in valoare de 40p, N ≤ 1000, M ≤ 3000
Exemplu
| vmin.in | vmin.out |
|---|---|
| 4 3 4 5 2 9 8 7 11 3 0 5 7 | 4 2 2 |
