Велике сортування (Розбір)

Solution

General Idea : We need to answer multiple queries asking for the $k$-th element in the array after sorting it in ascending order. The optimal approach is to sort the array once, then answer each query in constant time by direct indexing.

Algorithm :

• Read the array of size $n$.

• Sort the array in ascending order.

• For each query $k$, output the element at index k-1 in the sorted array.

Sorting dominates the complexity, while queries are handled efficiently.

Overall complexity is \mathcal{O}(n \log n + q).

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

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());

    while (q--) {
        int k;
        cin >> k;
        cout << a[k - 1];
    }
}

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

    solve();
    return 0;
}