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 | |
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.
O subsecvență este o submulțime de elemente ale șirului aflate pe poziții consecutive.
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, Q ≤ 200.000
- 1 ≤ L ≤ R ≤ N
- 1 ≤ X, Numerele din șirul lui Gigel ≤ 109
Subtaskul 1 (6 puncte)
- 1 ≤ N, Q ≤ 300
Subtaskul 2 (12 puncte)
- 1 ≤ N ≤ 5000
- Toate X-urile sunt sunt egale
Subtaskul 3 (16 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
Subsecvențele care indeplinesc condițiile la prima interogare sunt [2,2], [1,2], [4,4], [4,5]. La a 2-a sunt [2,2] si [4,4].