SHARE
TWEET

Untitled

a guest May 19th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. int n;
  7. vector<int> a;
  8. vector<vector<int> > st;
  9. vector<int> lg(1e6 + 1);
  10.  
  11. void build() {
  12.     lg[1] = 0;
  13.     for (int i = 2; i <= 1e6; ++i) lg[i] = lg[i/2] + 1;
  14.     for (int i = 0; i<n; ++i) st[0][i] = a[i];
  15.     for (int i = 1; i<20; ++i) {
  16.         for (int j = 0; j + (1 << i) <= n; ++j)
  17.             st[i][j] = max(st[i - 1][j], st[i - 1][j + (1<<(i-1))]);
  18.     }
  19. }
  20.  
  21. int get_max(int l, int r) {
  22.     int i = lg[r - l + 1];
  23.     return max(st[i][l], st[i][r - (1<<i) + 1]);
  24. }
  25.  
  26. signed main() {
  27.  
  28.     cin >> n;
  29.     a.resize(n);
  30.     st.resize(20, vector<int> (n));
  31.     for (int i = 0; i<n; ++i) cin >> a[i];
  32.     build();
  33.  
  34.     int k;
  35.     cin >> k;
  36.     for (int i = 0; i<k; ++i) {
  37.         int l, r;
  38.         cin >> l >> r;
  39.         --l, --r;
  40.         cout << get_max(l, r) << "\n";
  41.     }
  42.  
  43.     return 0;
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top