Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-05 20:01:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:consir.in, consir.outSursăAutumn Warmup 2007, Runda 3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.225 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Consir

Vultur a gasit in cartea de chimie o problema care nu stie sa o rezolve si are nevoie de ajutorul vostru. Se da o secventa A, formata din N numere naturale. Un consir este un sir de numere naturale i1, i2 ... ip (cu valori cuprinse intre 1 si N) cu proprietatea ca A[i1], A[i2] ... A[ip] sunt numere consecutive. Determinati K, lungimea maxima a unui consir ce se poate forma, precum si numarul de consiruri distincte de lungime 1, 2 ... K.

Date de intrare

Pe prima linie a fisierului consir.in se va afla numarul N avand semnificatia din enunt. Pe urmatoarele N linii se afla valorile secventei A, mai exact pe linia i+1 se afla valoarea lui A[i].

Date de iesire

Pe prima linie a fisierului consir.out se va afla valoarea K, avand semnificatia din enunt. In continuare vor urma K linii, pe linia i+1 aflandu-se numarul de consiruri distincte de lungime i.

Restrictii

  • 1 ≤ N ≤ 310 000
  • Termenii sirului au valori cuprinse intre 1 si 1 000 000
  • Se garanteaza ca fiecare raspuns are o valoare mai mica decat 263 (se incadreaza pe tipuri de date intregi pe 64 biti fara semn)
  • Lungimea unui consir este data de numarul de elemente
  • Doua consiruri X si Y sunt distincte daca exista o pozitie i astfel inca X[i] diferit de Y[i]

Exemplu

consir.inconsir.out
6
1
2
1
3
4
5
5
6
5
4
3
2

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?