Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | calin.in, calin.out | Sursă | CodeChef |
|---|---|---|---|
| Autor | autor necunoscut | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 524288 KB |
| Scorul tău | N/A | Dificultate |
   1.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Călin (clasele 9-12)
Nota 1: Problema este adaptată după Stable Market (Code Chef).
Nota 2: Punctajele subtaskurilor diferă de concursul original.
Călin publică un film pe TikTok în care vorbește timp de n minute despre cel mult 9 subiecte. La fiecare minut i (1 ≤ i ≤ n) el vorbește despre subiectul si.
Numim delir o subsecvență maximală de minute în care Călin vorbește despre același subiect. Numim delir de gravitate k un delir cu durata de k minute.
Dorim să răspundem la q interogări definite prin triplete l, r, k cu semnificația: Dacă luăm în calcul doar intervalul de la minutul l pînă la minutul r inclusiv, cîte deliruri de gravitate cel puțin k există?
Date de intrare
Fișierul de intrare calin.in conține pe prima linie numerele n și q, separate prin spațiu. A doua linie conține valorile s1 s2 ... sn, separate prin spații. Fiecare dintre următoarele q linii conține cîte un triplet de numere l r k cu semnificația de mai sus.
Date de ieșire
În fișierul de ieșire calin.out afișați răspunsurile la interogări, cîte unul pe linie, în aceeași ordine ca la intrare.
Restricții
- 1 ≤ n, q ≤ 200.000
- 1 ≤ si ≤ 9 pentru orice 1 ≤ i ≤ n
- 1 ≤ l ≤ r ≤ n și 1 ≤ k ≤ r − l + 1 pentru fiecare interogare
| subtask | puncte | restricții |
|---|---|---|
| 1 | 15 | n, q ≤ 15.000 |
| 2 | 55 | n, q ≤ 80.000 |
| 3 | 30 | Fără restricții suplimentare. |
Exemplu
| calin.in | calin.out |
|---|---|
| 8 5 6 4 4 4 1 1 1 4 2 6 2 3 6 2 3 6 3 3 8 3 3 8 1 |
2 2 0 1 3 |
Explicații
- Interogarea 1: Pe subsecvența (4 4 4 1 1) există un delir de gravitate 3 și un delir de gravitate 2. Așadar, există două deliruri de gravitate cel puțin 2.
- Interogările 2-3: Pe subsecvența (4 4 1 1) există două deliruri de gravitate 2. Subliniem că aceste deliruri nu au gravitate 3, căci considerăm doar pozițiile 3-6.
- Interogările 4-5: Pe subsecvența (4 4 1 1 1 4) există un delir de gravitate 1, un delir de gravitate 2 și un delir de gravitate 3.
