fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <memory>
  5.  
  6. struct Range {
  7.     int start, end;
  8.     bool Include(const Range& outer) const { return outer.start <= start && end <= outer.end; }
  9.     bool Exclude(const Range& outer) const { return outer.end < start || end < outer.start; }
  10.     bool IsLeaf() const { return start == end; }
  11.     int Count() const { return 1 + end - start; }
  12. };
  13.  
  14. class Node {
  15. public:
  16.     inline static std::vector<int> InitArray;
  17.  
  18. public:
  19.     explicit Node(Range r) : range(r) {
  20.         if (range.IsLeaf()) {
  21.             array.emplace_back(InitArray[range.start]);
  22.             return;
  23.         }
  24.         int mid = range.start + (range.end - range.start) / 2;
  25.         left = std::make_unique<Node>(Range{ range.start, mid });
  26.         right = std::make_unique<Node>(Range{ mid + 1, range.end });
  27.         array.resize(range.Count());
  28.         std::merge(left->array.begin(), left->array.end(), right->array.begin(), right->array.end(), array.begin());
  29.     }
  30.     int LessCount(const Range& query, int value) const {
  31.         if (range.Exclude(query)) return 0;
  32.         if (range.Include(query)) {
  33.             return static_cast<int>(std::lower_bound(array.begin(), array.end(), value) - array.begin());
  34.         }
  35.         return left->LessCount(query, value) + right->LessCount(query, value);
  36.     }
  37.     int GetMinimum() const { return array.front(); }
  38.     int GetMaximum() const { return array.back(); }
  39.  
  40. private:
  41.     Range range;
  42.     std::unique_ptr<Node> left;
  43.     std::unique_ptr<Node> right;
  44.     std::vector<int> array;
  45. };
  46.  
  47. int main() {
  48.     std::cin.tie(nullptr)->sync_with_stdio(false);
  49.     int n, q;
  50.     std::cin >> n >> q;
  51.  
  52. 	Node::InitArray.resize(n);
  53.     for (int i = 0; i < n; i++) std::cin >> Node::InitArray[i];
  54.  
  55.     Node root(Range{ 0, n - 1 });
  56.     const int minValue = root.GetMinimum();
  57.     const int maxValue = root.GetMaximum();
  58.  
  59.     for (int i = 0; i < q; ++i) {
  60.         int l, r, k;
  61.         std::cin >> l >> r >> k;
  62.         const Range query{ l - 1, r - 1 };
  63.  
  64.         int low = minValue;
  65.         for (int high = maxValue, mid; low < high; ) {
  66.             mid = low + (high - low) / 2;
  67.             if (root.LessCount(query, mid + 1) < k) {
  68.                 low = mid + 1;
  69.             }
  70.             else {
  71.                 high = mid;
  72.             }
  73.         }
  74.         std::cout << low << '\n';
  75.     }
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5164KB
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/zwZ1tw
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!