== include(page="template/taskheader" task_id="extraterestri1") ==
Poveste și cerință...
_Notă: această problemă are exact același enunț ca problema extraterestri. Ceea ce s-a modificat este memoria, care a fost mult limitată._
O invazie de $N$ farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităților. În fiecare astfel de OZN se află extratereștri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul [$XOY$]. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.
Pentru anihilarea OZN-urilor, autoritățile dispun de $K$ arme laser. Armele sunt poziționate pe sol (ilustrat pe ecranul radarului prin axa [$OX$]). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa [$OY$]. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toți extratereștrii aflați în OZN-ul respectiv.
Din păcate, în preajmă se află doar un militar specializat în arme laser, așa că autoritățile doresc să știe exact ce armă trebuie să folosească acesta pentru a distruge cât mai mulți extratereștri.
h2. Cerință
Ajutați autoritățile să determine numărul de extratereștri care pot fi anihilați cu fiecare armă din dotare.
h2. Date de intrare
Fișierul de intrare $extraterestri1.in$ ...
Fișierul de intrare $extraterestri1.in$ conține pe prima linie două numere naturale separate prin spațiu $N$ $K$ reprezentând numărul de OZN-uri și respectiv numărul de arme laser. Pe următoarele $N$ linii sunt descrise cele $N$ OZN-uri, câte unul pe linie. Un OZN este descris prin $5$ numere naturale separate prin câte un spațiu $x1$ $y1$ $x2$ $y2$ [$nr$], reprezentând în ordine coordonatele capetelor segmentului corespunzător $(x1, y1)$, $(x2, y2)$, iar $nr$ – numărul de extratereștri din el. Pe ultima linie se găsesc $K$ numere naturale $a1 a2 a3 ... aK$, separate prin câte un spațiu, reprezentând coordonatele pe axa $OX$ (abscisele) unde sunt amplasate armele laser.
h2. Date de ieșire
În fișierul de ieșire $extraterestri1.out$ ...
Fișierul de ieșire $extraterestri1.out$ va conține $K$ linii. Pe linia $i$ va fi scris numărul total de extratereștri care pot fi distruși cu arma [$i$], considerând armele numerotate în ordinea în care acestea apar în fișierul de intrare.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 20 000$
* $1 ≤ K ≤ 20 000$
* $1 ≤ orice coordonată din fișierul de intrare ≤ 2 000 000$
* $1 ≤ nr ≤ 100$, pentru orice OZN
* $x1 < x2$, pentru orice OZN
* Pe ecranul radarului segmentele ce descriu navele se pot intersecta.
* Dacă raza laser trece prin unul dintre capetele unui OZN atunci acesta este distrus.
* Pentru $50%$ dintre testele de intrare $1 ≤ N*K ≤ 10 000 000$
h2. Exemplu
table(example).
|_. extraterestri1.in |_. extraterestri1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. extraterestri1.in |_. extraterestri1.out |_. Explicații |
| 5 3
1 1 3 2 2
2 3 4 1 3
6 5 8 5 8
5 1 7 1 6
6 2 7 4 1
3 7 5
| 5
15
6
| !problema/extraterestri?extraterestri.jpg!
Arma care emite din punctul $(3,0)$ doboară farfuriile reprezentate de segmentele
(1,1)(3,2) și (2,3)(4,1) distrugând în total 5 extratereștri.
Arma care emite din punctul $(7,0)$ doboară farfuriile reprezentate de segmentele
(5,1)(7,1), (6,2)(7,4) și (6,5)(8,5) distrugând în total 15 extratereștri.
Arma care emite din punctul $(5,0)$ doboară farfuria reprezentată de segmentul
(5,1)(7,1) și distruge 6 extratereștri.
|
== include(page="template/taskfooter" task_id="extraterestri1") ==
