fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxn = 1e5 + 5;
  5. //
  6. int n, q, A[maxn], rmq[maxn][20];
  7. //
  8. void build (void)
  9. {
  10.     for (int i = 1; i <= n; ++i)
  11.         rmq[i][0] = i;
  12.     for (int u, v, j = 1; (1 << j) <= n; ++j)
  13.         for (int i = 1; i + (1 << j) - 1 <= n; ++i)
  14.             u = rmq[i][j - 1],
  15.             v = rmq[i + (1 << j - 1)][j - 1],
  16.             rmq[i][j] = (A[u] > A[v] ? v : u);
  17. }
  18. int get (int l, int r)
  19. {
  20.     int k = __lg(r - l + 1);
  21.     //
  22.     l = rmq[l][k];
  23.     r = rmq[r - (1 << k) + 1][k];
  24.     return A[l] > A[r] ? r : l;
  25. }
  26. //
  27. void process (void)
  28. {
  29.     cin >> n >> q;
  30.     for (int i = 1; i <= n; ++i)
  31.         cin >> A[i];
  32.     build();
  33.     for (int l, r; q--; cout << '\n')
  34.         cin >> l >> r,
  35.         cout << get(l, r);
  36. }
  37. //
  38. signed main (void)
  39. {
  40.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  41.     process();
  42. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VHyqOh
https://m...content-available-to-author-only...j.com/problem/308
language:
C++14 (gcc 8.3)
created:
6 hours 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!