SHARE
TWEET

Untitled

a guest May 19th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. class RMQ {
  5. public:
  6.     RMQ(int n) {
  7.         this->n = n;
  8.         a = std::vector<int>(n + 1);
  9.         log = std::vector<int>(n + 1);
  10.         height = fill_log(n);
  11.         s.resize(n + 1);
  12.         for (int i = 1; i <= n; ++i) {
  13.             s[i].resize(height + 1);
  14.         }
  15.     }
  16.  
  17.     int fill_log(int n) {
  18.         log[0] = -1;
  19.         for (int i = 1; i <= n; ++i) {
  20.             log[i] = log[i / 2] + 1;
  21.         }
  22.         return log[n];
  23.     }
  24.  
  25.     void add_element(int index, int  element) {
  26.         a[index] = element;
  27.     }
  28.  
  29.     std::pair<int, int> get_min_pair(std::pair<int, int>& lhs, std::pair<int, int>& rhs) {
  30.         if (a[lhs.second] <= a[rhs.first]) {
  31.             return lhs;
  32.         }
  33.         if (a[lhs.first] >= a[rhs.second]) {
  34.             return rhs;
  35.         }
  36.         if (a[lhs.first] <= a[rhs.first]) {
  37.             if (lhs.first != rhs.first) {
  38.                 return { lhs.first, rhs.first };
  39.             }
  40.             if (a[lhs.second] <= a[rhs.second]) {
  41.                 return lhs;
  42.             }
  43.             return rhs;
  44.         }
  45.         return { rhs.first, lhs.first };
  46.     }
  47.  
  48.  
  49.     void fill_s() {
  50.         for (int i = 1; i < n; ++i) {
  51.             if (a[i] < a[i + 1]) {
  52.                 s[i][1] = { i, i + 1 };
  53.             }
  54.             else {
  55.                 s[i][1] = { i + 1, i };
  56.             }
  57.         }
  58.  
  59.         for (int j = 2; (1 << j) < n + 1; ++j) {
  60.             for (int i = 1; i + (1 << j) - 1 < n + 1; ++i) {
  61.                 s[i][j] = get_min_pair(s[i][j - 1], s[i + (1 << (j - 1))][j - 1]);
  62.             }
  63.         }
  64.     }
  65.  
  66.     int query(int u, int v) {
  67.         if (u > v) {
  68.             std::swap(u, v);
  69.         }
  70.         int k = log[v - u + 1];
  71.         return a[get_min_pair(s[u][k], s[v - (1 << k) + 1][k]).second];
  72.     }
  73.  
  74. private:
  75.     std::vector<int>  log;
  76.     std::vector<std::vector<std::pair<int, int>>> s;
  77.     std::vector<int> a;
  78.     int n = 0;
  79.     int height = 0;
  80. };
  81.  
  82. int main() {
  83.     int n = 0;
  84.     int m = 0;
  85.     int u = 0;
  86.     int v = 0;
  87.     int element = 0;
  88.     std::cin >> n >> m;
  89.     RMQ g(n);
  90.  
  91.     for (int i = 1; i < n + 1; ++i) {
  92.         std::cin >> element;
  93.         g.add_element(i, element);
  94.     }
  95.     g.fill_s();
  96.     for (int i = 1; i < m + 1; ++i) {
  97.         std::cin >> u >> v;
  98.         std::cout << g.query(u, v);
  99.     }
  100.     return 0;
  101. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top