| 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 |
  2
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Ssecvint (clasele 11 și 12)
O subsecvență a unui șir S = (s1, s2, .., sn) este un subșir format din elemente aflate pe poziții consecutive în șir: si, si+1, .., si+k-1 unde k este un număr natural (secvența poate avea și lungimea 1).
Fie S un șir de intervale închise de forma [ Ai , Bi ]. 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 Ai și Bi , 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.
