Fişierul intrare/ieşire: | rangemode.in, rangemode.out | Sursă | Infoarena Cup 2013 |
Autor | Cosmin Silvestru Negruseri | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
RangeMode
Fie o secvenţă de N numere întregi. Să se răspundă la M întrebări de tipul: Care este cel mai frecvent element din intervalul [st, dr]?
Date de intrare
Fişierul de intrare rangemode.in conţine pe prima sa linie numerele N si M seminficând lungimea secvenţei, respectiv numărul de întrebări. Pe urmatoarea linie se va afla secventa de numere intregi. Urmatoarele M linii vor contine cate o pereche st dr reprezentând capetele intervalului pentru care dorim să aflăm răspunsul.
Date de ieşire
Fişierul de ieşire rangemode.out va conţine M linii, linia i conţinând răspunsul pentru întrebarea cu numărul i.
Restricţii
- 1 ≤ N, M ≤ 100.000
- Numerele din secventa sunt in intervalul [1, 100.000].
- Dacă există mai multe elemente de frecvenţă maximă pentru un anumit interval, se va afişa elementul de valoare minimă dintre acestea.
Exemplu
rangemode.in | rangemode.out |
---|---|
7 3 1 2 2 3 1 3 3 1 3 4 5 1 7 | 2 1 3 |