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 | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
Ssecvint
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.