Mikki0

Untitled

Sep 26th, 2021
956
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <execution>
  3. #include <future>
  4. #include <vector>
  5.  
  6. std::vector<int> maxlength;
  7. std::vector<std::vector<int>> sparse;
  8.  
  9. struct Request {
  10. public:
  11.     int left, right;
  12. };
  13.  
  14. int ProcessRequest(Request& request) {
  15.     return std::min(sparse[maxlength[request.right - request.left]][request.left], sparse[maxlength[request.right - request.left]][request.right - (1 << maxlength[request.right - request.left])]);
  16. }
  17.  
  18. std::vector<int> ProcessRequests(const std::vector<int>& numbers, const std::vector<Request>& requests) {
  19.     int power = 0;
  20.     int num = 1;
  21.     while (num < numbers.size()) {
  22.         ++power;
  23.         num *= 2;
  24.     }
  25.     sparse.resize(power + 1);
  26.     for (auto& el : sparse) {
  27.         el.resize(numbers.size());
  28.     }
  29.     maxlength.resize(numbers.size() + 1);
  30.     power = 0;
  31.     num = 1;
  32.     for (int i = 0; i < numbers.size(); ++i) {
  33.         sparse[0][i] = numbers[i];
  34.         if (i + 1 == num * 2) {
  35.             num *= 2;
  36.             ++power;
  37.         }
  38.         maxlength[i + 1] = power;
  39.     }
  40.     for (int i = 1; i <= power; ++i) {
  41.         size_t step = (1 << (i - 1));
  42.         for (size_t j = 0; j < numbers.size(); ++j) {
  43.             sparse[i][j] = sparse[i - 1][j];
  44.             if (j + step < numbers.size()) {
  45.                 sparse[i][j] = std::min(sparse[i][j], sparse[i - 1][j + step]);
  46.             }
  47.         }
  48.     }
  49.     std::vector<int> answer;
  50.     std::transform(std::execution::par, requests.begin(), requests.end(), answer.begin(), ProcessRequest);
  51.     return answer;
  52. }
  53.  
  54. #include <iostream>
  55.  
  56. int main() {
  57.     size_t n;
  58.     std::cin >> n;
  59.     std::vector<int> numbers(n);
  60.     for (size_t i = 0; i < n; ++i) {
  61.         std::cin >> numbers[i];
  62.     }
  63.     size_t m;
  64.     std::cin >> m;
  65.     std::vector<Request> requests;
  66.     for (size_t i = 0; i < m; ++i) {
  67.         int l, r;
  68.         std::cin >> l >> r;
  69.         requests.push_back({l, r});
  70.     }
  71.     std::vector<int> answer = ProcessRequests(numbers, requests);
  72.     for (auto el : answer) {
  73.         std::cout << el << ' ';
  74.     }
  75. }
  76.  
RAW Paste Data