Nu aveti permisiuni pentru a descarca fisierul grader_test5.in
Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2022-11-04 09:59:34.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | macseq.in, macseq.out | Sursă | Baraj Shumen Juniori ICHB-Vianu - 2022 |
| Autor | Armin Asgari, Ilie Luca Mihai | Adăugată de |  Comisie Juniori Vianu - ICHB •comisie_baraj_shumen_ichb_vianu_juniori |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Macseq
Gigel are un șir de N numere naturale, acesta vă cere ajutorul în rezolvarea a Q interogări de forma L, R, X. Pentru fiecare întrebare Gigel vrea să știe numarul de subsecvențe care sunt incluse in intervalul [L, R] și au maximul egal cu X.
Date de intrare
Fişierul de intrare macseq.in conține pe prima linie N și Q cu semnificațiile din enunț. Următoarea linie conține șirul lui Gigel. Pe următoarele Q linii sunt prezentate interogările de forma L, R, X.
Date de ieşire
În fişierul de ieşire macseq.out trebuie sa afișați pe fiecare linie separat raspunusul la întrebările lui Gigel.
Restricţii
- 1 ≤ N ≤ 200.000
- 1 ≤ Q ≤ 200.000
- Numerele din șirul lui Gigel ≤ 109
- 1 ≤ L ≤ R ≤ N
- 1 ≤ X ≤ 109
Subtaskul 1 (6 puncte)
- 1 ≤ N, Q ≤ 300
Subtaskul 2 (9 puncte)
- 1 ≤ N ≤ 2000
- Toate X-urile sunt sunt egale
Subtaskul 3 (14 puncte)
- 1 ≤ N, Q ≤ 2000
Substaskul 4 (22 puncte)
- 1 ≤ N, Q ≤ 200.000
- Toate X-urile sunt sunt egale
Exemplu
| macseq.in | macseq.out |
|---|---|
| 6 3 15 33 55 33 12 46 1 6 33 2 4 33 1 6 55 | 4 2 12 |
Explicaţie
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
