Atenție! Aceasta este o versiune veche a paginii., scrisă la 2018-01-26 04:48:38.
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 avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.2 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii