bolsa_de_brinquedos.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
array<int, 4*MAXN> seg;

void update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return;
    if (ini == fim)
    {
        seg[pos] = val;
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    update(e, ini, m, id, val);
    update(d, m+1, fim, id, val);
    seg[pos] = min(seg[e], seg[d]);
}

int query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return INF;
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    return min(query(e, ini, m, p, q), query(d, m+1, fim, p, q));
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> custo(M+1);
    for (int i = 1; i <= M; i++) cin >> custo[i];
    vector<int> v(N+1);
    for (int i = 1; i <= N; i++) cin >> v[i];
    int Q;
    cin >> Q;
    vector<vector<pair<int, int>>> queries(N+1); vector<int> resp(Q);
    for (int i = 0; i < Q; i++)
    {
        int L, R;
        cin >> L >> R;
        queries[R].emplace_back(L, i);
    }

    seg.fill(INF);
    vector<vector<int>> brinq(M+1);
    for (int i = 1; i <= N; i++)
    {
        brinq[v[i]].push_back(i);
        if (brinq[v[i]].size() >= K) update(1, 1, N, brinq[v[i]][brinq[v[i]].size() - K], custo[v[i]]);
        for (auto [L, id] : queries[i]) resp[id] = query(1, 1, N, L, i);
    }

    for (auto x : resp) cout << (x == INF ? -1 : x * K) << '\n';
}