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.2 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
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
Exemple
ssecvint.in | ssecvint.out |
---|---|
3
-1 4
2 2
-3 0 |
2 |
4
-1 4
2 2
3 6
-3 0 |
2 |
Explicație
În ambele exemple subsecvența de lungime maximă e formată din primele două intervale.