fork download
copy 
  1. using System.Buffers;
  2. using System.Runtime.CompilerServices;
  3. using static IO;
  4. public sealed class IO {
  5. public static IO Cin = new();
  6. static readonly StreamReader reader = new(Console.OpenStandardInput());
  7. public static readonly StreamWriter writer = new(Console.OpenStandardOutput());
  8. public static implicit operator int(IO _)
  9. {
  10.     int c;
  11.     while ((c=reader.Peek()) != -1 && c < '0' && c != '-') reader.Read();
  12.     int ret = 0;
  13.     bool negative = false;
  14.     if ((c = reader.Read()) == '-') negative = true;
  15.     else ret = c - '0';
  16.     while ('0' <= (c = reader.Read()) && c <= '9') ret = ret * 10 + (c - '0');
  17.     return negative ? -ret : ret;
  18. }
  19. public static readonly ArrayPool<int> IntArrayPool = ArrayPool<int>.Create(2_000_000, 300_000);
  20. }
  21. sealed class Program {
  22.     static void Main() {
  23.         int n = Cin, q = Cin;
  24.         Node.InitArray = IntArrayPool.Rent(n);
  25.         for (int i = 0; i < n; i++) Node.InitArray[i] = Cin;
  26.  
  27.         Node root = new(new(0, n - 1));
  28.         int min = root.Minimum, max = root.Maximum;
  29.         for(int i=0;i < q;i++) {
  30.             Range range = new(Cin - 1, Cin - 1);
  31.             int kth = Cin;
  32.             int low = min;
  33.             for(int high = max, mid; low < high; ) {
  34.                 mid = (low + high) / 2;
  35.                 if (root.LessCount(range, mid + 1) < kth) low = mid + 1;
  36.                 else high = mid;
  37.             }
  38.             writer.WriteLine(low);
  39.         }
  40.         writer.Flush();
  41.     }
  42. }
  43. public readonly record struct Range(int Start, int End)
  44. {
  45.     public readonly bool Include(in Range outer) => outer.Start <= Start && End <= outer.End;
  46.     public readonly bool Exclude(in Range outer) => outer.End < Start || End < outer.Start;
  47.     public readonly bool IsLeaf => Start == End;
  48.     public readonly int Count => 1 + End - Start;
  49. }
  50. sealed class Node {
  51.     public static int[] InitArray = null!;
  52.     readonly Range range;
  53.     readonly Node? left = null, right = null;
  54.     readonly int[] array;
  55.     readonly int n;
  56.     public Node(Range range) {
  57.         if ((this.range = range).IsLeaf) {
  58.             array = IntArrayPool.Rent(n = 1);
  59.             array[0] = InitArray[range.Start];
  60.             return;
  61.         }
  62.  
  63.         int mid = (range.Start + range.End) / 2;
  64.         left = new(range with { End = mid });
  65.         right = new(range with { Start = mid + 1 });
  66.  
  67.         array = IntArrayPool.Rent(n = range.Count);
  68.         int l = 0, r = 0;
  69.         for (int i = 0; i < n; i++) {
  70.             if ((l < left.n ? left.array[l] : int.MaxValue) < (r < right.n ? right.array[r] : int.MaxValue)) {
  71.                 array[i] = left.array[l++];
  72.             } else {
  73.                 array[i] = right.array[r++];
  74.             }
  75.         }
  76.     }
  77.     public int LessCount(Range query, int value) {
  78.         if (range.Exclude(query)) return 0;
  79.         if (range.Include(query)) {
  80.             if (range.IsLeaf) return array[0] < value ? 1 : 0;
  81.  
  82.             return LowerBound(value);
  83.         }
  84.         return left!.LessCount(query, value) + right!.LessCount(query, value);
  85.     }
  86.     public int Minimum => array[0];
  87.     public int Maximum => array[n-1];
  88.  
  89.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
  90.     private int LowerBound(int value) {
  91.         int low = 0;
  92.         for (int high = n; low < high; ) {
  93.             int mid = (low + high) / 2;
  94.             if (array[mid] < value) low = mid + 1;
  95.             else high = mid;
  96.         }
  97.         return low;
  98.     }
  99. }
Success #stdin #stdout 0.07s 64452KB
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/0MyYnj
language:
C# (NET 6.0)
created:
18 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!