Fişierul intrare/ieşire:vopsire.in, vopsire.outSursăONIS 2015 Runda Finala
AutorAdrian AirineiAdăugată deONIS2015ONIS2015 ONIS2015
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vopsire

GS (Gusterul Suprem) a facut o introspectie asupra constructiei sociale a realitatii si s-a apucat de vopsit garduri. Mai exact, GS are M capete de interval x1, x2, y1 si y2 (cu x1 < x2 si y1 < y2). Lui GS i se mai pun la dispozitie si N intervale reprezentate prin x si y. Spunem ca un interval x y se potriveste cu un set de capete de interval x1 x2 y1 y2 daca x1 ≤ x ≤ x2 si y1 ≤ y ≤ y2.
GS vrea sa stie pentru fiecare interval din cele N cate din cele M seturi de capete de interval se potrivesc cu el.

Date de intrare

Fişierul de intrare vopsire.in contine pe prima linie doua numere M si N, avand semnificatia din enunt.
Pe urmatoarele M linii urmeaza cate 4 numere reprezentand capetele de interval, x1 x2 y1 y2.
Pe urmatoarele N linii urmeaza cate doua numere reprezentand intervalele x y.

Date de ieşire

În fişierul de ieşire vopsire.out se vor gasi N linii.
Pe linia i se va gasi numarul de seturi de capete de interval care se potrivesc cu al i-lea interval din cele N, in ordinea in care apar in fisierul de intrare.

Restricţii

  • 1 ≤ N, M ≤ 50 000
  • Toate numerele din fisierul de intrare sunt mai mici sau egale cu 500 000
  • Toate valorile sunt pozitive

Exemplu

vopsire.invopsire.out
3 4
1 7 5 10
2 4 6 9
5 7 3 8
3 8
5 5
1 9
7 4
2
2
1
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?