Editing 1071 - OZN

O invazie de <code>N</code> 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 <code>XOY</code>. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.

Pentru anihilarea OZN-urilor, autorităţile dispun de <code>K</code> arme laser. Armele sunt poziţionate pe sol (ilustrat pe ecranul radarului prin axa <code>OX</code>). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa <code>OY</code>. 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.

= Cerinţă =
Ajutaţi autorităţile să determine numărul de extratereştri care pot fi anihilaţi cu fiecare armă din dotare.

= Date de intrare =
Fișierul de intrare <code>ozn.in</code> conține pe prima linie două numere naturale separate prin spaţiu <code>N K</code> reprezentând numărul de OZN-uri şi respectiv numărul de arme laser. Pe următoarele <code>N</code> linii sunt descrise cele N OZN-uri, câte unul pe linie. Un OZN este descris prin <code>5</code> numere naturale separate prin câte un spaţiu <code>x1 y1 x2 y2 nr</code>, reprezentând în ordine coordonatele capetelor segmentului corespunzător <code>(x1, y1)</code>, <code>(x2, y2)</code>, iar <code>nr</code> – numărul de extratereştri din el. Pe ultima linie se găsesc <code>K</code> numere naturale <code>a<sub>1</sub></code> <code>a<sub>2</sub></code> <code>a<sub>3</sub></code> … <code>a<sub>K</sub></code>, separate prin câte un spaţiu, reprezentând coordonatele pe axa <code>OX</code> (abscisele) unde sunt amplasate armele laser.

= Date de ieșire =
Fișierul de ieșire <code>ozn.out</code> va conține <code>K</code> linii. Pe linia <code>i</code> va fi scris numărul total de extratereştri care pot fi distruşi cu arma <code>i</code>, considerând armele numerotate în ordinea în care acestea apar în fişierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N ≤ 20 000</code>
* <code>1 ≤ K ≤ 20 000</code>
* <code>1 ≤</code> orice coordonată din fişierul de intrare <code>≤ 2 000 000</code>
* <code>1 ≤ nr ≤ 100</code>, pentru orice OZN
* <code>x<sub>1 < x2</sub></code><sub>, pentru orice OZN</sub>
* 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 <code>1 ≤ N*K ≤ 10 000 000</code>

= Exemplu: =
<code>ozn.in</code>
 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
<code>ozn.out</code>
 5
 15
 6
Explicație

Arma care emite din punctul <code>(3,0)</code> doboară farfuriile reprezentate de segmentele <code>{(1,1)(3,2)}</code> şi <code>{(2,3)(4,1)}</code> distrugând în total <code>5</code> extratereştri.

Arma care emite din punctul <code>(7,0)</code> doboară farfuriile reprezentate de segmentele <code>{(5,1)(7,1)}, {(6,2)(7,4)}</code> şi <code>{(6,5)(8,5)}</code> distrugând în total <code>15</code> extratereştri.

Arma care emite din punctul <code>(5,0)</code> doboară farfuria reprezentată de segmentul <code>{(5,1)(7,1)}</code> şi distruge <code>6</code> extratereştri.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

MAXX = 2000010
MAXN = 100010

f = open("ozn.in", "r")
g = open("ozn.out", "w")

A = [0] * MAXX
N, K = map(int, f.readline().split())
X1, Y1, X2, Y2, nr, i = 0, 0, 0, 0, 0, 0

for i in range(1, N + 1):
    X1, Y1, X2, Y2, nr = map(int, f.readline().split())
    A[X1] += nr
    A[X2 + 1] -= nr

for i in range(1, MAXX):
    A[i] += A[i - 1]

for i in range(1, K + 1):
    X1 = int(f.readline())
    g.write(str(A[X1]) + '\n')

g.close()
f.close()
</syntaxhighlight>