Mikki0

Untitled

Sep 26th, 2021
899
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <thread>
  3. #include <vector>
  4.  
  5. struct Request {
  6. public:
  7.     int left, right;
  8. };
  9.  
  10. std::vector<std::vector<int>> sparse;
  11. std::vector<size_t> maxlength;
  12. std::vector<int> answer;
  13.  
  14. void BuildMaxlength(const std::vector<int>& numbers, size_t power, size_t L, size_t R) {
  15.     for (size_t i = L; i < R; ++i) {
  16.         sparse[0][i] = numbers[i];
  17.         if (i + 1 == (1 << power)) {
  18.             ++power;
  19.         }
  20.         maxlength[i + 1] = power;
  21.     }
  22. }
  23.  
  24. void BuildSparse(size_t n, size_t i, size_t L, size_t R) {
  25.     size_t step = (1 << (i - 1));
  26.     for (size_t j = L; j < R; ++j) {
  27.         sparse[i][j] = sparse[i - 1][j];
  28.         if (j + step < n) {
  29.             sparse[i][j] = std::min(sparse[i][j], sparse[i - 1][j + step]);
  30.         }
  31.     }
  32. }
  33.  
  34. void ProcessSomeRequests(const std::vector<Request>& requests, size_t L, size_t R) {
  35.     for (size_t i = L; i < R; ++i) {
  36.         size_t len = maxlength[requests[i].right - requests[i].left];
  37.         answer[i] = std::min(sparse[len][requests[i].left], sparse[len][requests[i].right - (1 << len)]);
  38.     }
  39. }
  40.  
  41. std::vector<int> ProcessRequests(const std::vector<int>& numbers, const std::vector<Request>& requests) {
  42.     const size_t n = numbers.size();
  43.     const size_t r = requests.size();
  44.     size_t power = 0;
  45.     while ((1 << power) < n) {
  46.         ++power;
  47.     }
  48.     sparse.resize(power + 1);
  49.     for (size_t i = 0; i <= power; ++i) {
  50.         sparse[i].resize(n);
  51.     }
  52.     maxlength.resize(n + 1);
  53.     answer.resize(r);
  54.     size_t po = 0;
  55.     while ((1 << po) <= n / 2) {
  56.         ++po;
  57.     }
  58.     std::thread a(BuildMaxlength, numbers, 0, 0, n / 2);
  59.     std::thread b(BuildMaxlength, numbers, po, n / 2, n);
  60.     a.join();
  61.     b.join();
  62.     for (int i = 1; i <= power; ++i) {
  63.         std::thread x(BuildSparse, n, i, 0, n / 2);
  64.         std::thread y(BuildSparse, n, i, n / 2, n);
  65.         x.join();
  66.         y.join();
  67.     }
  68.     std::thread c(ProcessSomeRequests, requests, 0, r / 2);
  69.     std::thread d(ProcessSomeRequests, requests, r / 2, r);
  70.     c.join();
  71.     d.join();
  72.     return answer;
  73. }
  74.  
  75. #include <iostream>
  76.  
  77. int main() {
  78.     size_t n;
  79.     std::cin >> n;
  80.     std::vector<int> numbers(n);
  81.     for (size_t i = 0; i < n; ++i) {
  82.         std::cin >> numbers[i];
  83.     }
  84.     size_t m;
  85.     std::cin >> m;
  86.     std::vector<Request> requests;
  87.     for (size_t i = 0; i < m; ++i) {
  88.         int l, r;
  89.         std::cin >> l >> r;
  90.         requests.push_back({l, r});
  91.     }
  92.     std::vector<int> ans = ProcessRequests(numbers, requests);
  93.     for (auto el : ans) {
  94.         std::cout << el << ' ';
  95.     }
  96. }
  97.  
RAW Paste Data