== include(page="template/taskheader" task_id="cars") ==
Poveste şi cerinţă...
Pentru a ajunge la cea de-a XXXIII-a ediţie a concursului Grigore Moisil, cei $N+M$ membri ai comisiei au decis să profite de noua autostradă Cluj-Napoca - Târgu Mureş. Fiecare membru al comisiei conduce maşina proprie, reprezentată sub forma unui punct. Maşinile se clasifică în două categorii:
* $N$ dintre ele sunt maşini rapide, cu viteza constantă egală cu $A m/s$.
* $M$ dintre ele sunt maşini lente, cu viteza constantă egală cu $B m/s$.
Fiecare maşină porneşte de la o anumită poziţie întreagă, reprezentând distanţa faţă de Cluj-Napoca, măsurată în metri.
Autostrada are lungimea de $L$ metri şi, din păcate, oferă o singură bandă de circulaţie. În schimb, este partiţionată în două tipuri de segmente:
* Segmente cu linie întreruptă, pe care se pot efectua depăşiri. Dacă o maşină mai rapidă ajunge din urmă o maşină mai lentă pe un astfel de segment, maşina rapidă va efectua o depăşire. Depăşirea are loc instantaneu, fără ca maşinile implicate să îşi schimbe vitezele. Depăşirile se pot efectua inclusiv în capetele unui segment cu linie întreruptă.
* Segmente cu linie continuă, pe care nu se pot efectua depăşiri. Dacă o maşină mai rapidă ajunge din urmă o maşină mai lentă pe un astfel de segment, maşina rapidă va încetini instantaneu astfel încât va avea aceeaşi viteză ca maşina lentă. Până la finalul segmentului, cele două maşini îşi vor continua drumul concomitent, având aceeaşi poziţie şi aceeaşi viteză. În cazul în care urmează un segment cu linie întreruptă, maşina rapidă va efectua depăşirea în primul punct al segmentului şi va reveni instantaneu la viteza iniţială.
*Se garantează că toate întâlnirile dintre oricare două maşini vor avea loc la poziţii întregi.*
Să se determine pentru fiecare din cele $N+M$ maşini numărul de secunde necesare pentru a ajunge la destinaţie.
h2. Date de intrare
Fişierul de intrare $cars.in$ ...
Fişierul de intrare $cars.in$ conţine pe prima linie valorile întregi $N$, $M$, $K$, $L$, $A$ şi $B$.
Următoarea linie conţine $N$ valori întregi separate prin spaţii, reprezentând poziţiile celor $N$ maşini rapide, în ordine crescătoare.
Următoarea linie conţine $M$ valori întregi separate prin spaţii, reprezentând poziţiile celor $M$ maşini lente, în ordine crescătoare.
Fiecare din următoarele $K$ linii conţine câte o pereche de numere întregi $l$~$i$~ $r$~$i$~, reprezentând capetele unui segment de drum cu linie continuă. Segmentele nu se suprapun şi nu au capete comune. Orice punct al autostrăzii care nu face parte dintr-un segment cu linie continuă, face parte dintr-un segment cu linie întreruptă.
h2. Date de ieşire
În fişierul de ieşire $cars.out$ ...
Fişierul de ieşire $cars.out$ trebuie să conţină $N+M$ valori reale, fiecare pe o linie nouă. Fiecare din primele $N$ valori reprezintă durata călătoriei unei maşini rapide, în aceeaşi ordine ca în datele de intrare. Fiecare din următoarele $M$ valori reprezintă durata călătoriei unei maşini lente, în aceeaşi ordine ca în datele de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 20 000$
* $1 ≤ K ≤ 100$
* $N + M < L ≤ 1 000 000 000$
* $1 ≤ B < A ≤ 1 000$
* $0 ≤ poziţia oricărei maşini < L$
* $0 ≤ l$~$1$~ $< r$~$1$~ $< … < l$~$i$~ $< r$~$i$~ $< … l$~$k$~ $< r$~$k$~ $≤ L$
* Nu există maşini care pornesc de la aceeaşi poziţie.
* Timpul fiecărei maşini va fi considerat corect dacă diferă prin cel mult $10^-4^$ de răspunsul corect.
* Pentru unele teste în valoare de 5 puncte, $N = M = 1$.
* Pentru alte teste în valoare de 5 puncte, $K = 1, l$~1~ $= 0, r$~1~ $= L$.
* Pentru alte teste în valoare de 10 puncte, $N, M ≤ 100, L ≤ 1 000$.
* Pentru alte teste în valoare de 30 de puncte, $N, M ≤ 1 000, L ≤ 500 000$.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Exemplul va reprezenta teste în valoare de 10 puncte "din oficiu".
* $_Admin update: A se considera ca daca o masina rapida prinde din urma o masina lenta fix la inceputul unui segment cu linie continua, nu o poate depasi atunci_$
h2. Exemplu
table(example). |_. cars.in |_. cars.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1 1 2 100 12 8
18
25
0 20
25 50
| 7.291667
9.375000
|
h3. Explicaţie
...
Există o singură maşină rapidă şi o singură maşină lentă. Maşina rapidă porneşte de la poziţia $18$ şi are viteza egală cu $12 m/s$. Maşina lentă porneşte de la poziţia $25$ şi are viteza egală cu $8 m/s$.
Cele două segmente de drum cu linie continuă se desfăşoară pe intervalele $(0, 20)$ şi $(25, 50)$. Implicit, segmentele cu linie întreruptă se desfăşoară pe intervalele $[20, 25]$ şi $[50, 100]$.
Maşinile se întâlnesc la poziţia $39$ (după $1.75$ secunde), într-un punct de pe un segment cu linie continuă. Ca urmare, vor continua drumul împreună cu viteza de $8 m/s$ până la poziţia $50$, unde începe un segment cu linie întreruptă.
În acest punct, maşina rapidă o depăşeşte instantaneu pe cea lentă, şi revine la viteza iniţială de $12 m/s$. Ajunge la destinaţie după $7.291667$ secunde de la începutul călătoriei.
Maşina lentă ajunge la destinaţie după $9.375$ secunde de la începutul călătoriei.
== include(page="template/taskfooter" task_id="cars") ==
