fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n, q;
  9.     cin >> n >> q;
  10.  
  11.     vector<int> input(n);
  12.     for (int &x: input) cin >> x;
  13.  
  14.     vector<vector<int>> segment_tree(4 * n);
  15.  
  16.     function<void(int, int, int)> build = [&](int vertex, int left, int right) {
  17.         if (left > right) return;
  18.         if (left == right)
  19.         {
  20.             segment_tree[vertex] = { input[left] };
  21.             return;
  22.         }
  23.  
  24.         int middle = left + (right - left) / 2;
  25.         int left_child = 2 * vertex + 1;
  26.         int right_child = 2 * vertex + 2;
  27.  
  28.         build(left_child, left, middle);
  29.         build(right_child, middle + 1, right);
  30.  
  31.         vector<int> combined;
  32.  
  33.         auto commit_monotone = [&](int value) {
  34.             if (combined.empty())
  35.             {
  36.                 combined.push_back(value);
  37.                 return;
  38.             }
  39.  
  40.             if (combined.back() < value)
  41.             {
  42.                 combined.push_back(value);
  43.                 return;
  44.             }
  45.         };
  46.  
  47.         for (int &x: segment_tree[left_child])
  48.             commit_monotone(x);
  49.         for (int &x: segment_tree[right_child])
  50.             commit_monotone(x);
  51.  
  52.         segment_tree[vertex] = combined;
  53.     };
  54.  
  55.     build(0, 0, n - 1);
  56.  
  57.     auto query = [&](int query_left, int query_right) {
  58.         function<list<int>(int, int, int)> traverse = [&](int vertex, int left, int right) {
  59.             if (left > right) return list<int> {};
  60.             if (query_left > right) return list<int> {};
  61.             if (query_right < left) return list<int> {};
  62.             if (query_left <= left && right <= query_right)
  63.             {
  64.                 return list<int> { vertex };
  65.             }
  66.  
  67.             int middle = left + (right - left) / 2;
  68.             int left_child = 2 * vertex + 1;
  69.             int right_child = 2 * vertex + 2;
  70.  
  71.             auto left_result = traverse(left_child, left, middle);
  72.             left_result.splice(left_result.end(), traverse(right_child, middle + 1, right));
  73.  
  74.             return left_result;
  75.         };
  76.  
  77.         return traverse(0, 0, n - 1);
  78.     };
  79.  
  80.     for (int i = 0; i < q; i++)
  81.     {
  82.         int left, right;
  83.         cin >> left >> right;
  84.         left--; right--;
  85.  
  86.         auto lists = query(left, right);
  87.  
  88.         int last_seen_max = -1;
  89.         int count = 0;
  90.         for (auto &vertex: lists)
  91.         {
  92.             if (last_seen_max == -1)
  93.             {
  94.                 last_seen_max = segment_tree[vertex].back();
  95.                 count = segment_tree[vertex].size();
  96.                 continue;
  97.             }
  98.  
  99.             auto first_it = lower_bound(segment_tree[vertex].begin(), segment_tree[vertex].end(), last_seen_max);
  100.             if (first_it == segment_tree[vertex].end()) continue;
  101.             count += segment_tree[vertex].end() - first_it;
  102.             last_seen_max = segment_tree[vertex].back();
  103.         }
  104.  
  105.         cout << count << "\n";
  106.     }
  107. }
Runtime error #stdin #stdout #stderr 4.77s 1957976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Z9DesU
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!