Mikki0

Untitled

Sep 26th, 2021 (edited)
445
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. std::vector<int> ProcessRequests(const std::vector<int>& numbers, const std::vector<Request>& requests) {
  15.     int power = 0;
  16.     int num = 1;
  17.     while (num < numbers.size()) {
  18.         ++power;
  19.         num *= 2;
  20.     }
  21.     sparse.resize(power + 1);
  22.     for (auto& el : sparse) {
  23.         el.resize(numbers.size());
  24.     }
  25.     maxlength.resize(numbers.size() + 1);
  26.     power = 0;
  27.     num = 1;
  28.     for (int i = 0; i < numbers.size(); ++i) {
  29.         sparse[0][i] = numbers[i];
  30.         if (i + 1 == num * 2) {
  31.             num *= 2;
  32.             ++power;
  33.         }
  34.         maxlength[i + 1] = power;
  35.     }
  36.     for (int i = 1; i <= power; ++i) {
  37.         size_t step = (1 << (i - 1));
  38.         for (size_t j = 0; j < numbers.size(); ++j) {
  39.             sparse[i][j] = sparse[i - 1][j];
  40.             if (j + step < numbers.size()) {
  41.                 sparse[i][j] = std::min(sparse[i][j], sparse[i - 1][j + step]);
  42.             }
  43.         }
  44.     }
  45.     std::vector<int> answer;
  46.     for (int i = 0; i < requests.size(); ++i) {
  47.         int len = maxlength[requests[i].right - requests[i].left];
  48.         answer.push_back(std::min(sparse[len][requests[i].left], sparse[len][requests[i].right - (1 << len)]));
  49.     }
  50.     return answer;
  51. }
  52.  
  53. #include <iostream>
  54.  
  55. int main() {
  56.     size_t n;
  57.     std::cin >> n;
  58.     std::vector<int> numbers(n);
  59.     for (size_t i = 0; i < n; ++i) {
  60.         std::cin >> numbers[i];
  61.     }
  62.     size_t m;
  63.     std::cin >> m;
  64.     std::vector<Request> requests;
  65.     for (size_t i = 0; i < m; ++i) {
  66.         int l, r;
  67.         std::cin >> l >> r;
  68.         requests.push_back({l, r});
  69.     }
  70.     std::vector<int> answer = ProcessRequests(numbers, requests);
  71.     for (auto el : answer) {
  72.         std::cout << el << ' ';
  73.     }
  74. }
RAW Paste Data