TLE占领了最后两个高地

RT,归并排序

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

const int N = 5000500;
ll a[N], n;
ll tmp[N]; // 额外的数组
ll k;

void mergesort(ll a[], ll l, ll r ) {
    if ( l >= r )
        return; // 只有 1 个元素
    // step1: 先分治
    ll mid = l + r >> 1;
    mergesort( a, l, mid );
    mergesort( a, mid + 1, r );

    // step2：从最小的区间，开始从左向右比对元素，按条件从左往右进行放置
    ll k = l, i = l, j = mid + 1;
    while ( i <= mid && j <= r )
        if ( a[i] <= a[j] )
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];

    // step3：将剩余已有顺序的元素，直接从左往右直接放置
    while ( i <= mid )
        tmp[k++] = a[i++];
    while ( j <= r )
        tmp[k++] = a[j++];

    // step4：将已排好序的元素，还原到原序列中
    for (i = l; i <= r; i++)
        a[i] = tmp[i];
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    mergesort( a, 1, n );

    cout << a[k + 1];
    return 0;
}