Submission #74122302

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Query {
    ll t;
    int idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    vector<int> A(N);
    vector<ll> cnt(M + 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }
    
    int Q;
    cin >> Q;
    
    vector<ll> ans(Q, -1);
    vector<Query> queries;
    queries.reserve(Q);
    
    for (int i = 0; i < Q; i++) {
        ll X; cin >> X;
        if (X <= N) {
            ans[i] = A[X - 1];
        } else {
            queries.push_back({X - N, i});
        }
    }
    
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.t < b.t;
    });
    
    map<ll, vector<int>> groups;
    for (int i = 1; i <= M; i++) {
        groups[cnt[i]].push_back(i);
    }
    for (auto& [k, v] : groups) {
        sort(v.begin(), v.end());
    }
    
    ll cur_t = 1;
    size_t qptr = 0;
    
    while (qptr < queries.size()) {
        auto it = groups.begin();
        
        auto it2 = next(it);
        if (it2 == groups.end()) {
            ll cycle_start = cur_t;
            while (qptr < queries.size()) {
                ll t = queries[qptr].t;
                ans[queries[qptr].idx] = (t - cycle_start) % M + 1;
                qptr++;
            }
            break;
        }
        
        ll mn = it->first;
        ll next_mn = it2->first;
        ll k = next_mn - mn;
        
        vector<int> per = move(it->second);
        int perlen = per.size();
        ll seg_len = k * (ll)perlen;
        ll seg_r = cur_t + seg_len - 1;
        
        while (qptr < queries.size() && queries[qptr].t <= seg_r) {
            ll t = queries[qptr].t;
            ll pos = (t - cur_t) % perlen;
            ans[queries[qptr].idx] = per[pos];
            qptr++;
        }
        
        groups.erase(it);
        
        auto& target = groups[next_mn];
        vector<int> merged;
        merged.reserve(per.size() + target.size());
        merge(per.begin(), per.end(), target.begin(), target.end(), back_inserter(merged));
        target = move(merged);
        
        cur_t = seg_r + 1;
    }
    
    for (ll x : ans) {
        cout << x << "\n";
    }
    
    return 0;
}

Submission Info

Judge Result