Advertisement
OIQ

DO_max

OIQ
Oct 30th, 2019
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <math.h>
  4. #include <vector>
  5. #include <utility>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. pair <int, int> find(int v, int L, int R, int l, int r, vector <pair <int, int>> a) {
  11.     if (l >= L and r <= R)
  12.         return a[v];
  13.     if (l > R || r < L)
  14.         return pair<int, int> (-1, v);
  15.     pair <int, int> m1 = find(2 * v + 1, L, R, l, (l + r) / 2, a);
  16.     pair <int, int> m2 = find(2 * v + 2, L, R, (l + r) / 2 + 1, r, a);
  17.  
  18.     if (m1.first > m2.first)
  19.         return m1;
  20.     return m2;
  21.  
  22. }
  23.  
  24. int main() {
  25.  
  26.     int n;
  27.  
  28.     cin >> n;
  29.  
  30.     int N = (int)pow(2, ceil(log2(n)));
  31.     vector <pair <int, int>> a(2 * N - 1, pair <int, int> (-1, 0));
  32.  
  33.     for (int i = a.size() / 2; i < a.size() / 2 + n; i++) {
  34.         pair <int, int> p(0, i - a.size() / 2);
  35.         cin >> p.first;
  36.         a[i] = p;
  37.  
  38.     }
  39.  
  40.     for (int i = a.size() / 2 - 1; i >= 0; i--) {
  41.         if (a[i * 2 + 1].first > a[i * 2 + 2].first)
  42.             a[i] = a[i * 2 + 1];
  43.         else
  44.             a[i] = a[i * 2 + 2];
  45.     }
  46.  
  47.  
  48.     int k, L, R;
  49.     cin >> k;
  50.  
  51.     for (int i = 0; i < k; i++) {
  52.         cin >> L >> R;
  53.         L--; R--;
  54.        
  55.         pair <int, int> ans(find(0, L, R, 0, a.size() / 2, a));
  56.         cout << ans.first << " " << ans.second + 1 << endl;
  57.     }
  58.  
  59.  
  60.     return 0;
  61. }
Advertisement
RAW Paste Data Copied
Advertisement