Art_Uspen

Untitled

Sep 28th, 2021
840
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <cmath>
  3. #include <execution>
  4. #include<iostream>
  5.  
  6. using namespace std;
  7. using namespace std::execution;
  8.  
  9. vector<vector<int>> st;
  10. vector<int> degrees;
  11.  
  12. struct Request {
  13.     Request() = default;
  14.  
  15.     Request(int l, int r) : left(l), right(r) {}
  16.  
  17.     int left;
  18.     int right;
  19. };
  20.  
  21. vector<int> get_degrees(int N) {
  22.     vector<int> degrees(N + 1);
  23.     int degree = 0;
  24.     int index = 0;
  25.     while (pow(2, degree) <= N) {
  26.         while (index < pow(2, degree + 1) && index <= N) {
  27.             degrees[index] = degree;
  28.             ++index;
  29.         }
  30.         ++degree;
  31.     }
  32.     return degrees;
  33. }
  34.  
  35. vector<vector<int>> build_sp_table(const vector<int> &arr) {
  36.     st.resize(arr.size());
  37.     for (int i = 0; i < arr.size(); ++i) {
  38.         st[0].push_back(arr[i]);
  39.     }
  40.     int i = 1;
  41.     while (pow(2, i) <= arr.size()) {
  42.         st[i].reserve(arr.size());
  43.         int j = 0;
  44.         int v_left = st[i - 1][j];
  45.         int v_right = st[i - 1][j + pow(2, i - 1)];
  46.         while (j + pow(2, i - 1) < st[i - 1].size()) {
  47.             st[i].push_back(min(v_left, v_right));
  48.             ++j;
  49.             v_left = st[i - 1][j];
  50.             v_right = st[i - 1][j + pow(2, i - 1)];
  51.         }
  52.         ++i;
  53.     }
  54.     return st;
  55. }
  56.  
  57. int get_min(const Request &req) {
  58.     int R_i = req.right - 1;
  59.     int L_i = req.left;
  60.     int de_max = degrees[R_i - L_i];
  61.     return min(st[de_max][L_i], st[de_max][R_i - pow(2, de_max) + 1]);
  62. }
  63.  
  64. vector<int> ProcessRequests(const vector<int> &numbers, const vector<Request> &requests) {
  65.     vector<int> res;
  66.     res.resize(requests.size());
  67.     st = build_sp_table(numbers);
  68.     degrees = get_degrees(numbers.size());
  69.     transform(par, requests.begin(), requests.end(), res.begin(), get_min);
  70.     return res;
  71. }
RAW Paste Data