fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * @username: sriman_chetan
  6.  * @author: Chetan Raikwar
  7.  * @date: 28-10-2020
  8.  */
  9. class Solution {
  10.  
  11.     public static void main(String[] args) throws IOException {
  12.  
  13.         try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  14.                 PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out))) {
  15.  
  16.             StringTokenizer input = new StringTokenizer(reader.readLine());
  17.  
  18.             int n = Integer.parseInt(input.nextToken());
  19.             int m = Integer.parseInt(input.nextToken());
  20.  
  21.             input = new StringTokenizer(reader.readLine());
  22.  
  23.             Pair[] a = new Pair[n];
  24.  
  25.             for (int i = 0; i < n; i++) {
  26.                 int num = Integer.parseInt(input.nextToken());
  27.                 a[i] = new Pair(num, i);
  28.             }
  29.  
  30.             Arrays.sort(a);
  31.  
  32.             MergesortTree mergesortTree = new MergesortTree(a, n);
  33.             //mergesortTree.showTree();
  34.  
  35.             while (m-- > 0) {
  36.  
  37.                 input = new StringTokenizer(reader.readLine());
  38.                 int i = Integer.parseInt(input.nextToken());
  39.                 int j = Integer.parseInt(input.nextToken());
  40.                 int k = Integer.parseInt(input.nextToken());
  41.  
  42.                 k = (k > (j - i + 1)) ? -1 : mergesortTree.kthSmallest(i, j, k);
  43.                 writer.println(k);
  44.                 // writer.println("------------------------------------------------------");
  45.  
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. class MergesortTree {
  52.  
  53.     final int n;
  54.     final Pair[] a;
  55.     List<Pair>[] tree;
  56.  
  57.     public MergesortTree(Pair[] list, int size) {
  58.         n = size - 1;
  59.         a = list;
  60.         tree = new List[4 * size + 1];
  61.  
  62.         constructTree(0, 0, n);
  63.     }
  64.  
  65.     public Integer kthSmallest(int left, int right, int k) {
  66.         return kthSmallestQuery(0, 0, n, left - 1, right - 1, k);
  67.     }
  68.  
  69.     private Integer leftChild(int node) {
  70.         return 2 * node + 1;
  71.     }
  72.  
  73.     private Integer rightChild(int node) {
  74.         return 2 * node + 2;
  75.     }
  76.  
  77.     private Integer upperBound(final List<Pair> a, final int key) {
  78.  
  79.         int low = 0, high = a.size() - 1;
  80.  
  81.         if (key < a.get(low).index) {
  82.             return low;
  83.         }
  84.  
  85.         if (key >= a.get(high).index) {
  86.             return high;
  87.         }
  88.  
  89.         while (low <= high) {
  90.  
  91.             int mid = (low + high) / 2;
  92.  
  93.             if (a.get(mid).index <= key) {
  94.  
  95.                 if ((mid + 1) < n && a.get(mid + 1).index > key) {
  96.                     return mid + 1;
  97.                 }
  98.                 low = mid + 1;
  99.             } else {
  100.                 high = mid - 1;
  101.             }
  102.         }
  103.  
  104.         return a.size() - 1;
  105.     }
  106.  
  107.     private Integer lowerBound(final List<Pair> a, final int key) {
  108.  
  109.         int low = 0, high = a.size() - 1;
  110.  
  111.         if (key <= a.get(low).index) {
  112.             return low;
  113.         }
  114.  
  115.         if (key >= a.get(high).index) {
  116.             return high;
  117.         }
  118.  
  119.         while (low <= high) {
  120.  
  121.             int mid = (low + high) / 2;
  122.  
  123.             if (a.get(mid).index >= key) {
  124.  
  125.                 if ((mid - 1) >= 0 && a.get(mid - 1).index < key) {
  126.                     return mid;
  127.                 }
  128.                 high = mid - 1;
  129.             } else {
  130.                 low = mid + 1;
  131.             }
  132.         }
  133.  
  134.         return a.size() - 1;
  135.     }
  136.  
  137.     private void constructTree(int node, int low, int high) {
  138.  
  139.         if (low == high) {
  140.             tree[node] = new ArrayList<>();
  141.             tree[node].add(a[low]);
  142.             return;
  143.         }
  144.  
  145.         int mid = (low + high) / 2;
  146.         int left = leftChild(node);
  147.         int right = rightChild(node);
  148.  
  149.         tree[node] = new ArrayList<>();
  150.         tree[left] = new ArrayList<>();
  151.         tree[right] = new ArrayList<>();
  152.  
  153.         constructTree(left, low, mid);
  154.         constructTree(right, mid + 1, high);
  155.  
  156.         int i = 0, j = 0;
  157.         int leftEnd = tree[left].size(), rightEnd = tree[right].size();
  158.  
  159.         while (i < leftEnd && j < rightEnd) {
  160.  
  161.             if (tree[left].get(i).index <= tree[right].get(j).index) {
  162.                 tree[node].add(tree[left].get(i++));
  163.             } else {
  164.                 tree[node].add(tree[right].get(j++));
  165.             }
  166.         }
  167.  
  168.         while (i < leftEnd) {
  169.             tree[node].add(tree[left].get(i++));
  170.         }
  171.  
  172.         while (j < rightEnd) {
  173.             tree[node].add(tree[right].get(j++));
  174.         }
  175.     }
  176.  
  177.     private Integer kthSmallestQuery(int node, int low, int high, int left, int right, int k) {
  178.  
  179.         if (low == high) {
  180.             return tree[node].get(0).value;
  181.         }
  182.  
  183.         int mid = (low + high) / 2;
  184.         int LEFT = leftChild(node);
  185.         int RIGHT = rightChild(node);
  186.  
  187.         int greaterThanK = upperBound(tree[LEFT], right);
  188.         int smallerThanK = lowerBound(tree[LEFT], left);
  189.  
  190.         int m = greaterThanK - smallerThanK;
  191.  
  192.         // System.out.println((left + 1) + "\t" + (right + 1) + "\t" + (node + 1) + "\t" + (smallerThanK + 1) + "\t" + (greaterThanK + 1) + "\t" + m + "\t" + (k));
  193.         if (m >= k) {
  194.             return kthSmallestQuery(LEFT, low, mid, left, right, k);
  195.         } else {
  196.             return kthSmallestQuery(RIGHT, mid + 1, high, left, right, k - m);
  197.         }
  198.  
  199.     }
  200.  
  201.     public void showTree() {
  202.  
  203.         for (int i = 0; i < tree.length; i++) {
  204.             if (tree[i] != null) {
  205.                 System.out.println(tree[i]);
  206.             }
  207.         }
  208.     }
  209. }
  210.  
  211. class Pair implements Comparable<Pair> {
  212.  
  213.     final int value, index;
  214.  
  215.     public Pair(int value, int index) {
  216.  
  217.         this.value = value;
  218.         this.index = index;
  219.     }
  220.  
  221.     @Override
  222.     public int compareTo(Pair p) {
  223.         return this.value - p.value;
  224.     }
  225.  
  226.     @Override
  227.     public String toString() {
  228.         return "(" + value + " " + index + ")";
  229.     }
  230. }
  231.  
Success #stdin #stdout 0.06s 32920KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
6
7
4
https://ideone.com/8vfkDj
problem MKTHNUM, based on SPOJ submission 26819896 (JAVA), 2020-10-27 21:28:31
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

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!