infoarena

Avem N ferestre date prin coordonatele coltului stanga-sus si dreapta-jos: (x1,y1) si (x2,y2).
Stiind rezolutia ecranului X*Y si faptul ca toate ferestrele incap integral pe ecran(0 <= x1,x2 <= X si 0 <= y1,y2 <= Y), sa se afle care este numarul maxim de ferestre care se suprapun in oricare din regiunile ecranului.
Sa va afisa acest numar maxim de ferestre gasit in regiuni si suma ariilor ce contin acest maxim(nu se cer coordonatele regiunilor).

Observatii:
1) N < 10.000.000
2) X <= 1280 si Y <= 1024
3) N este in general foarte mare, si poate fi mai mare decat numarul de pixeli X*Y
4) Timpul de rulare permite doar complexitate O(N)
5) Memorie suficienta: 32MB

Intrare
N X Y
x11 y11 x12 y12
x21 y21 x22 y22
...
xn1 yn1 xn2 yn2

Iesire
MAX SUPRAFATA_MAX

Exemplu:
Intrare:
2 10 10
1 1 8 8
2 2 3 3
Iesire:
2 4

Pentru cele 2 ferestre(notate a si b pe vizualizare) ecranul arata asa:
A A A A A A A A o o
A B B A A A A A o o
A B B A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
o o o o o o o o o o
o o o o o o o o o o

Unde se vede clar ca regiunea maxima coincide cu fereastra B(deoarece fereastra A era sub ea) si are aria 4.

Problema ajutatoare:

Se da un fisier de lungime D si N comenzi de scriere in acest fisier. Comenzile sunt de forma: a b insemnand ca se vor schimba in fisier octetii incepand cu a(inclusiv) si terminand cu b(inclusiv).
Sa se afle MAX care este numarul maxim de schimbari a oricarui octet si cati octeti au fost schimbati de MAX ori.

Observatii:
1) D < 1000000
2) N < 10000000 (deci N poate fi mult mai mare decat D)
3) timpul de rulare permite doar complexitate O(n)
3) memorie suficienta: 16MB

Intrare:
N D
a1 b1
a2 b2
...
an bn

Iesire
MAX NR_OCTETI_MAX

Exemplu
Intrare
4 3
1 3
2 3
3 3
1 1

Iesire
3 1

Explicatii:
Fisierul este de 3 octeti [- - -]
comanda 1: [x x x]
comanda 2: [- x x]
comanda 3: [- - x]
comanda 4: [x - -]
Se observa ca octetul 3 s-a schimbat de 3 ori deci MAX=3 si NR_OCTETI_MAX = 1

Ambele probleme se rezolvă cu șmenul lui Mars.