POJ: K-th Number

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
5
6
3
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;#define B 707int n, m;int main(int argc, char* argv[]) {
scanf("%d%d", &n, &m);
vector<int> data(n);
vector<int> sorted(n);
int bucket_num = (n + B - 1) / B;
vector<vector<int> > buckets(bucket_num, vector<int>(B));
if (n % B != 0) buckets[bucket_num - 1].resize(n % B);
getchar();
for (int i = 0; i < n; ++i) {
scanf("%d", &data[i]);
sorted[i] = data[i];
buckets[i / B][i % B] = data[i];
}
sort(sorted.begin(), sorted.end());
for (int i = 0; i < bucket_num; ++i) sort(buckets[i].begin(), buckets[i].end());
while (m--) {
int i, j, k;
getchar();
scanf("%d%d%d", &i, &j, &k);
int start = -1;
int end = n - 1;
while (end > start + 1) {
int middle = start + (end - start) / 2;
int value = sorted[middle];
int c = 0;
int left = i - 1;
int right = j;

while (left < right && (left % B != 0))
if (data[left++] <= value) ++c;
while (left < right && (right % B != 0))
if (data[--right] <= value) ++c;

while (left < right) {
c += upper_bound(buckets[left / B].begin(), buckets[left / B].end(), value) - buckets[left / B].begin();
left += B;
}
if (c >= k) end = middle;
else start = middle;
}
printf("%d\n", sorted[end]);
}
return 0;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store