Fişierul intrare/ieşire:diagonala.in, diagonala.outSursăAlgoritmiada 2010, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Diagonala

Electra are o matrice patratica cu N linii si N coloane cu elemente 0 sau 1. Matricea respecta o proprietate ciudata: pentru orice linie i, toate elementele egale cu 1 se afla in intervalul compact aflat intre coloanele Xi si Yi ( Xi ≤ Yi ). Electra defineste in acesta matrice o diagonala ca fiind o linie cu panta egala cu 45 sau -45 de grade. Ea ar dori sa gaseasca cea mai lunga diagonala aflata numai pe elemente egale cu 1 in matrice. Electra va cere voua ajutorul si pentru a intelege mai bine va ofera cateva exemple de diagonale:

Exemplul 1Exemplul 2
0 0 0 0 1 1 0 0
0 0 1 1 1 0 0 0
0 0 0 1 1 1 1 0
0 0 0 0 0 1 1 0
0 1 1 1 1 1 1 0
0 0 0 1 1 1 1 1
0 1 1 1 1 0 0 0
1 1 1 0 0 0 0 0
0 0 0 0 1 1 0 0
0 0 1 1 1 0 0 0
0 0 0 1 1 1 1 0
0 0 0 0 0 1 1 0
0 1 1 1 1 1 1 0
0 0 0 1 1 1 1 1
0 1 1 1 1 0 0 0
1 1 1 0 0 0 0 0

Date de intrare

Fişierul de intrare diagonala.in va contie pe prima linie numarul natural N. Urmatoarele N linii vor contine fiecare cate doua numere Xi si Yi, separate printr-un spatiu, reprezentand faptul ca pe linia i din matrice, elementele egale cu 1 se afla intre coloanele Xi si Yi.

Date de ieşire

În fişierul de ieşire diagonala.out veti afisa un singur numar reprezentand lungimea unei diagonale maxime ce respecta conditiile din enunt.

Restricţii

  • 1 ≤ N ≤ 200 000
  • 1 ≤ Xi ≤ Yi ≤ N
  • Liniile si coloanele sunt numerotate de la 1 la N
  • Pentru 20% din teste N ≤ 100
  • Pentru 60% din teste N ≤ 100 000

Exemplu

diagonala.indiagonala.out
8
5 6
3 5
4 7
6 7
2 7
4 8
2 5
1 3
6

Explicaţie

Vezi exemplele de mai sus.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content