Advertisement
den4ik2003

Untitled

Jan 23rd, 2022
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using std::cin;
  6. using std::cout;
  7. using std::endl;
  8. using std::vector;
  9. using std::string;
  10. using std::swap;
  11. using std::pair;
  12. using std::min;
  13. using std::max;
  14. using pii = pair<int, int>;
  15.  
  16.  
  17. pii merge(const pii& l, const pii& r, const vector<int> &a) {
  18.     pii ret = {-1, -1};
  19.     vector<int> inds = {l.first, l.second, r.first, r.second};
  20.     vector<pii> elements;
  21.     for (auto i : inds) {
  22.         if (i != -1) {
  23.             bool in = false;
  24.             for (auto el : elements) {
  25.                 if (el.first == a[i] && el.second == i) {
  26.                     in = true;
  27.                     break;
  28.                 }
  29.             }
  30.             if (!in) {
  31.                 elements.push_back((pii){a[i], i});
  32.             }
  33.         }
  34.     }
  35.     std::sort(elements.begin(), elements.end());
  36.     ret.first = elements[0].second;
  37.     if (elements.size() >= 2) {
  38.         ret.second = elements[1].second;
  39.     }
  40.     return ret;
  41. }
  42.  
  43.  
  44. int main() {
  45.     std::ios_base::sync_with_stdio(false);
  46.     cin.tie(0);
  47.     cout.tie(0);
  48.     int n, m;
  49.     cin >> n >> m;
  50.     vector<int> a(n);
  51.     for (int i = 0; i < n; ++i) cin >> a[i];
  52.     vector<int> pow;
  53.     for (int p = 1; p <= n; p <<= 1) {
  54.         pow.push_back(p);
  55.     }
  56.     vector<int> find_p(n + 1);
  57.     int deg = 0;
  58.     for (int i = 1; i <= n; ++i) {
  59.         if (pow[deg] * 2 <= i) {
  60.             ++deg;
  61.         }
  62.         find_p[i] = deg;
  63.     }
  64.     vector<vector<pii> > sparse_table(pow.size());
  65.     for (int p = 0; p < pow.size(); ++p) {
  66.         for (int i = 0; i + pow[p] <= n; ++i) {
  67.             if (p == 0) {
  68.                 sparse_table[p].push_back({i, -1});
  69.             } else {
  70.                 pii left = sparse_table[p - 1][i];
  71.                 pii right = sparse_table[p - 1][i + pow[p - 1]];
  72.                 sparse_table[p].push_back(merge(left, right, a));
  73.             }
  74.         }
  75.     }
  76.     while (m--) {
  77.         int l, r;
  78.         cin >> l >> r;
  79.         l--;
  80.         int p = find_p[r - l];
  81.         pii left = sparse_table[p][l];
  82.         pii right = sparse_table[p][r - pow[p]];
  83.         int res = merge(left, right, a).second;
  84.         if (res == -1) {
  85.             cout << res << '\n';
  86.         } else {
  87.             cout << a[res] << '\n';
  88.         }
  89.     }
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement