Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | diagonala.in, diagonala.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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 1 | Exemplul 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 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
Exemplu
| diagonala.in | diagonala.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.
