diagonala

Diagonala

== include(page="template/taskheader" task_id="diagonala") ==

Poveste şi cerinţă...

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:
 
table(example). |_. 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
|

h2. Date de intrare

Fişierul de intrare $diagonala.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $diagonala.out$ ...

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

h2. 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$

h2. Exemplu
table(example). |_. diagonala.in |_. diagonala.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 8
5 6
3 5
4 7
6 7
2 7
4 8
2 5
1 3
| 6

|
h3. Explicaţie

...

Vezi exemplele de mai sus.

== include(page="template/taskfooter" task_id="diagonala") ==

4852