fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 500005;
  5. const int MAXLOG = 20;
  6.  
  7. int n, q;
  8. int s[MAXN];
  9. int st[MAXLOG][MAXN];
  10. int lg2[MAXN];
  11.  
  12. void preprocess() {
  13.     for (int i = 2; i <= n; i++)
  14.         lg2[i] = lg2[i / 2] + 1;
  15.     for (int i = 0; i < n; i++)
  16.         st[0][i] = s[i];
  17.     for (int j = 1; j < MAXLOG; j++)
  18.         for (int i = 0; i + (1 << j) <= n; i++)
  19.             st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  20. }
  21.  
  22. int query(int l, int r) {
  23.     int j = lg2[r - l + 1];
  24.     return min(st[j][l], st[j][r - (1 << j) + 1]);
  25. }
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.  
  31.     int t;
  32.     cin >> t;
  33.     while (t--) {
  34.         cin >> n >> q;
  35.         for (int i = 0; i < n; i++)
  36.             cin >> s[i];
  37.         preprocess();
  38.         while (q--) {
  39.             int l, r;
  40.             cin >> l >> r;
  41.             int mn = query(l - 1, r - 1);
  42.             int ans = mn;
  43.             while (l <= r) {
  44.                 if (s[l - 1] == mn) {
  45.                     l++;
  46.                     mn = (l <= r) ? query(l - 1, r - 1) : INT_MAX;
  47.                 } else {
  48.                     ans = max(ans, s[l - 1]);
  49.                     l++;
  50.                 }
  51.             }
  52.             cout << ans << '\n';
  53.         }
  54.     }
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 11840KB
comments (?)
stdin
copy 
2
5 3
1 3 2 2 1
2 4
3 4
4 5
9 4
5 6 3 5 4 4 3 2 1
1 3
2 6
3 7
6 9
stdout
copy 
3
2
2
6
6
5
4
https://ideone.com/BQ9lo9
language:
C++14 (gcc 8.3)
created:
1 year 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!