Fişierul intrare/ieşire:kinetic.in, kinetic.outSursăAlgoritmiada 2013, Runda 1
AutorCosmin GheorgheAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kinetic

Se dau N puncte care circula pe axa Ox. Pozitia celui de-al i-lea punct la momentul de timp t este dat de formula: ai + bi * t. Vi se mai dau deasemenea M query-uri de forma x y t. Pentru fiecare vi se cere sa ziceti cate puncte sunt intre coordonatele x si y (inclusiv) la momentul de timp t.

Date de intrare

Fişierul de intrare kinetic.in va contine pe prima linie 2 numere naturale N, si M, numarul de puncte, respectiv numarul de query-uri.
Urmatoarele N linii vor contine fiecare 2 valori. Astfel cea de-a i + 1 linie va contine valorile ai, respectiv bi.
Urmatoarele M linii vor contine fiecare 3 valori, x, y si t reprezentand intervalul de pe axa Ox la timpul t pentru care se intreaba.

Date de ieşire

În fişierul de ieşire kinetic.out trebuie sa se gaseasca M linii, cate una pentru fiecare query. Astfel cea de-a i-a linie din fisierul de iesire trebuie sa contina raspunsul pentru cel de-al i-lea query.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ 200.000
  • -10.000 ≤ ai, bi ≤ 10.000
  • -1.000.000.000 ≤ x, y ≤ 1.000.000.000
  • 0 ≤ t ≤ 1.000.000

Exemplu

kinetic.inkinetic.out
3 3
-9 -1
-2 -5
5 -8
91 -66 10
-73 38 4
86 23 7
2
3
0

Explicaţie

La momentul de timp 10 punctele se vor afla la coordonatele -9 + 10 * (-1) = -19, -2 + 10 * (-5) = -52 si 5 + 10 * (-8) = -75. Dintre acestea doar primele 2 se afla intre 91 si -66 pe axa Ox.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?