fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. int allocArray[1'660'965 + 100'000];
  6. int allocIndex = 0;
  7. int* NewInt(int size) noexcept {
  8.     int* ret = allocArray + allocIndex;
  9.     allocIndex += size;
  10.     return ret;
  11. }
  12.  
  13. struct Range {
  14.     int start, end;
  15.     bool Include(Range outer) const noexcept { return outer.start <= start && end <= outer.end; }
  16.     bool Exclude(Range outer) const noexcept { return outer.end < start || end < outer.start; }
  17.     bool IsLeaf() const noexcept { return start == end; }
  18.     int Count() const noexcept { return 1 + end - start; }
  19. };
  20. class Node {
  21. public:
  22.     inline static int* InitArray;
  23.  
  24. public:
  25.     explicit Node(Range r) noexcept : range(r) {
  26.         if (range.IsLeaf()) {
  27.             (array = NewInt(n = 1))[0] = InitArray[range.start];
  28.             return;
  29.         }
  30.  
  31.         int mid = range.start + (range.end - range.start) / 2;
  32.         left = new Node({ range.start, mid });
  33.         right = new Node({ mid + 1, range.end });
  34.  
  35.         array = NewInt(n = range.Count());
  36.         std::merge(left->array, left->array + left->n, right->array, right->array + right->n, array);
  37.     }
  38.     ~Node() {
  39.         delete left;
  40.         delete right;
  41.     }
  42.     int LessCount(Range query, int value) const noexcept {
  43.         if (range.Exclude(query)) { return 0; }
  44.         if (range.Include(query)) {
  45.             return static_cast<int>(std::lower_bound(array, array + n, value) - array);
  46.         }
  47.  
  48.         return left->LessCount(query, value) + right->LessCount(query, value);
  49.     }
  50.     int GetMinimum() const noexcept { return array[0]; }
  51.     int GetMaximum() const noexcept { return array[n-1]; }
  52. private:
  53.     Range range;
  54.     Node* left = nullptr, * right = nullptr;
  55.     int* array;
  56.     int n;
  57. };
  58.  
  59. int main() noexcept {
  60.     std::cin.tie(nullptr)->sync_with_stdio(false);
  61.     int n, q;
  62.     std::cin >> n >> q;
  63.  
  64.     Node::InitArray = NewInt(n);
  65.     for (int i = 0; i < n; ++i) {
  66.         std::cin >> Node::InitArray[i];
  67.     }
  68.  
  69.     Node* const root = new Node({ 0, n - 1 });
  70.  
  71.     const int minValue = root->GetMinimum();
  72.     const int maxValue = root->GetMaximum();
  73.  
  74.     for (int i = 0; i < q; ++i) {
  75.         int l, r, k;
  76.         std::cin >> l >> r >> k;
  77.         const Range query{ l - 1, r - 1 };
  78.  
  79.         int low = minValue;
  80.         for (int high = maxValue, mid; low < high; ) {
  81.             mid = low + (high - low) / 2;
  82.             if (root->LessCount(query, mid + 1) < k) {
  83.                 low = mid + 1;
  84.             }
  85.             else {
  86.                 high = mid;
  87.             }
  88.         }
  89.         std::cout << low << '\n';
  90.     }
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/tocGa0
5
6
3
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!