Pomalé riešenie

Ako prvé si predstavíme priamočiare riešenie bez žiadnych trikov. Budeme jednoducho vstupné pole lineárne prehľadávať počnúc od indexu $l$ a počítať, koľkokrát sme už narazili na zastávku v správnej vzdialenosti $v$ od Jozefovho domu. Akonáhle narazíme na $k$-tu takú, vypíšeme jej index. Ak ale prekonáme index $r$ pred tým, ako nájdeme odpoveď, odpovieme $-1$. Toto riešenie by bolo optimálne, v prípade, keby sme dostali len $q = 1$ otázok. To, že otázok môže byť veľa, nám ale napovedá, že sa asi dá najprv so vstupnými údajmi vykonať nejaká transformácia, ktorá nám potom umožní odpovede zisťovať rýchlejšie ako v lineárnom čase.

Vzorové riešenie

Kľúčový trik k riešeniu úlohy je nasledujúci: Pre každú vzialenosť $v$ od domu si vytvoríme pole, v ktorom sa nachádzajú čísla (indexy) zastávok, ktoré majú túto vzdialenosť. Napríklad ak je na vstupe pole: $[3, 4, 5, 4, 5]$ tak by sme si vytvorili v pamäti štruktúru podobnú nasledujúcej:

`X[3]: 1
X[4]: 2 4
X[5]: 3 5`

Na jej uskladnenie môžeme použiť buď hash mapu (dict) alebo jednoduché pole veľkosti $10^6$, pretože to je maximálna hodnota $v$.

Všimnime si, že každé pole $X[v]$ je usporiadané. Teraz vieme na otázky odpovedať nasledujúcim postupom: Pozrieme sa do poľa $X[v]$ a nájdeme v ňom najmenšiu hodnotu väčšiu alebo rovnú $l$. Ako na to? Postupné prechádzanie po jednom funguje, ale má zložitosť $O(n)$, takže si moc nepomôžeme. Zachráni nás ale binárne vyhľadávanie, ktoré to spraví v $O(\log n)$. Zastávka, ktorú takto nájdeme, je prvá taká, cez ktorú prejde autobus s Jozefom a je v správnej vzdialenosti od jeho domu. My chceme ale $k$-tu, nie prvú, takže sa v tomto poli $X[v]$ pozrieme o $k-1$ pozícii ďalej a nájdeme presne to, čo hľadáme. Ešte musíme ale vyriešiť dve prekážky: Ak by sme pri tomto procese vybehli z poľa, tak vieme, že taká zastávka neexistuje a odpovieme $-1$. Druhý problém je $r$ z otázky, no jednoducho sa stačí pozrieť na číslo zastávky, ktorú sme našli a ak je väčšie ako $r$, tak opäť vypíšeme $-1$, pretože zastávka už je mimo Jozefovej platnosti lístka.

Celková časová zložitosť riešenia (s použitím hash mapy) je $O(n+q\log n)$. $n$ pochádza z predpočítania štruktúry $X$ a $q\log n$ sú jednotlivé odpovede na otázky. Pamäťová zložitosť je $O(n)$, pretože jediné čo si pamätáme je $X$, pričom dokopy sa v ňom nachádza presne $n$ prvkov. Keby sme pre $X$ nepoužili hash mapu ale pole, zložitosti by boli trochu iné. Museli by sme na začiatku inicializovať pole veľkosti $10^6$, čo je určite viac ako $n$, pretože $n$ dosahuje len $10^5$. Taktiež si ho musíme pamätať. Ak by sme pomenovali $w = 10^6$ maximálnu hodnotu $v$, tak by časová zložitosť bola $O(w+n+q\log n)$ a pamäťová $O(w+n)$.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> V(1000001);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        V[x].push_back(i+1);
    }
    for (int i = 0; i < q; i++) {
        int l, r, v, k;
        cin >> l >> r >> v >> k;
        k--;
        int f = upper_bound(V[v].begin(), V[v].end(), l-1) - V[v].begin();
        if (f + k >= V[v].size() || V[v][f+k] > r)
            cout << -1 << '\n';
        else
            cout << V[v][f+k] << '\n';
    }
}

import bisect
from collections import defaultdict

def readints():
    return map(int, input().split())

n, q = readints()
X = list(readints())
# dict, ale ked pristupime k neexistujucemu prvku,
# tak automaticky vyrobi prazdny list
V = defaultdict(list)
for i, x in enumerate(X, 1):
    V[x].append(i)

for _ in range(q):
    l, r, v, k = readints()
    k-=1
    # Binarne vyhladavanie
    f = bisect.bisect(V[v], l-1)
    if f+k >= len(V[v]) or V[v][f+k] > r:
        print(-1)
    else:
        print(V[v][f+k])