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.

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 ozn.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 a₁ a₂ a₃ … a_K, separate prin câte un spaţiu, reprezentând coordonatele pe axa OX (abscisele) unde sunt amplasate armele laser.

Date de ieșire

Fișierul de ieșire ozn.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.

Restricții și precizări

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
x_{1_{< x_{2_{, 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

Exemplu

ozn.in

ozn.out

5
15
6

Explicație

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema OZN:

#include <fstream>

#define MAXX 2000010
#define MAXN 100010

using namespace std;

ifstream f("ozn.in");
ofstream g("ozn.out");

int A[MAXX];
int N,K;
int X1,Y1,X2,Y2,nr,i;

int main()
{

    f>>N>>K;
    for (i=1; i <= N; ++i){

        f>>X1>>Y2>>X2>>Y2>>nr;
        A[X1]+=nr;
        A[X2+1]-=nr;
    }

    for (i = 1; i < MAXX; ++i)
        A[i] += A[i-1];

    for (i = 1; i <= K; ++i){
        f>>X1;
        g<<A[X1]<<'\n';
    }
    g.close(); f.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1071 OZN

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1071 OZN de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1071 OZN