Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | ssecvint.in, ssecvint.out | Sursă | Olimpiada pe scoala clasele a 11-a si a 12-a, 2018 |
|---|---|---|---|
| Autor | din folclor | Adăugată de |
Victor Manz
•
vmanz
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
   2.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Ssecvint (clasele 11 și 12)
Dacă S = (s 1, s 2, ... s N) este un șir, numim subsecvență a sa un subșir de forma (s i, s i+1, s i+2, ... s j), unde 1 ≤ i ≤ j ≤ N.
Fie S un șir de intervale închise de forma [A i , B i]. Se cere lungimea maximă pe care o poate avea o subsecvență a sa, cu proprietatea că intervalele care fac parte din subsecvență au intersecția nevidă.
Date de intrare
Fișierul de intrare ssecvint.in conține pe prima linie numărul de intervale N, iar pe următoarele N linii câte două numere întregi A i și B i, separate prin câte un spațiu. Acestea reprezintă capetele intervalelor date.
Date de ieșire
În fișierul de ieșire ssecvint.out se va scrie un singur număr natural LMAX reprezentând lungimea maximă a unei subsecvențe de intervale cu intersecția nevidă.
Restricții
- 1 ≤ N ≤ 100 000
- -1 000 000 000 ≤ A i ≤ B i ≤ 1 000 000 000
Exemplu
| ssecvint.in | ssecvint.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
