Submission #74126541

---

Source Code Expand

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

struct events {
    int n;
    vector<int> bit;
    events(int n) : n(n), bit(n+1, 0) {}
    void update(int i) { for (i++; i <= n; i += i&-i) bit[i]++; }
    int query(int i) { int s=0; for (i++; i>0; i -= i&-i) s+=bit[i]; return s; }
    int kth(int k) {
        int pos = 0;
        for (int pw = 1<<20; pw; pw >>= 1)
            if (pos+pw <= n && bit[pos+pw] <= k) { pos += pw; k -= bit[pos]; }
        return pos;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> cnt(M + 1, 0);
    vector<int> A(N);
    for (int i = 0; i < N; i++) { cin >> A[i]; cnt[A[i]]++; }

    int maxi = *max_element(cnt.begin()+1, cnt.end());

    vector<pair<int,int>> ans1;
    for (int i = 1; i <= M; i++) ans1.push_back({cnt[i], i});
    sort(ans1.begin(), ans1.end());

    vector<pair<long long,int>> vis;
    long long tot = 0;
    {
        int j = 0;
        while (j < M && ans1[j].first < maxi) {
            int curr = ans1[j].first;
            int j0 = j;
            while (j < M && ans1[j].first == curr) j++;
            int curr1 = (j < M) ? min(ans1[j].first, maxi) : maxi;
            long long aa = curr1 - curr;
            vis.push_back({tot, j});
            tot += aa * (long long)j;
        }
    }
    long long P = tot;

    int num = (vis.empty() ? 0 : vis.back().second);
    vector<int> valv;
    vector<int> j;  

    {
        vector<pair<int,int>> vl; 
        for (int i = 0; i < (int)vis.size(); i++) {
            int lo = (i == 0 ? 0 : vis[i-1].second);
            int hi = vis[i].second;
            for (int k = lo; k < hi; k++)
                vl.push_back({ans1[k].second, i});
        }
        sort(vl.begin(), vl.end()); 
        for (auto [v, l] : vl) { valv.push_back(v); j.push_back(l); }
    }


    vector<vector<int>> pos1(vis.size());
    for (int i = 0; i < (int)valv.size(); i++)
        pos1[j[i]].push_back(i);


    int q; cin >> q;
    vector<long long> Xq(q);
    for (auto &x : Xq) cin >> x;


    vector<int> ans(q);
    vector<tuple<int,int,int>> qq;

    for (int qi = 0; qi < q; qi++) {
        long long X = Xq[qi];
        if (X <= N) {
            ans[qi] = A[X-1];
        } else if (X <= N + P) {
            long long off = X - N - 1;
            int lo = 0, hi = (int)vis.size()-1, lev = 0;
            while (lo <= hi) {
                int mid = (lo+hi)/2;
                if (vis[mid].first <= off) { lev=mid; lo=mid+1; }
                else hi=mid-1;
            }
            long long flag = off - vis[lev].first;
            int flag1 = vis[lev].second;
            int ind = (int)(flag % flag1);
            qq.push_back({lev, ind, qi});
        } else {
            long long aa = X - (N + P) - 1;
            ans[qi] = (int)(aa % M) + 1;
        }
    }

    sort(qq.begin(), qq.end());
    events bit((int)valv.size());
    int cur_lev = -1, lqi = 0;
    for (auto &[lev, ind, qi] : qq) {
        while (cur_lev < lev) {
            cur_lev++;
            for (int pos : pos1[cur_lev]) bit.update(pos);
        }
        ans[qi] = valv[bit.kth(ind)];
    }

    for (int x : ans) cout << x << "\n";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:41:17: warning: unused variable 'j0' [-Wunused-variable]
   41 |             int j0 = j;
      |                 ^~
./Main.cpp:51:9: warning: unused variable 'num' [-Wunused-variable]
   51 |     int num = (vis.empty() ? 0 : vis.back().second);
      |         ^~~
./Main.cpp:105:23: warning: unused variable 'lqi' [-Wunused-variable]
  105 |     int cur_lev = -1, lqi = 0;
      |                       ^~~

Judge Result