fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.     int n, q;
  10.     if (!(cin >> n >> q)) return 0;
  11.  
  12.     vector<int> p(n + 1);
  13.     for (int i = 1; i <= n; i++) {
  14.         cin >> p[i];
  15.     }
  16.  
  17.     vector<int> start_blk, end_blk;
  18.     int i = 1;
  19.     while (i <= n) {
  20.         int s = i;
  21.         while (i < n && p[i] > p[i+1]) {
  22.             i++;
  23.         }
  24.         start_blk.push_back(s);
  25.         end_blk.push_back(i);
  26.         i++;
  27.     }
  28.  
  29.     int K = start_blk.size();
  30.  
  31.     vector<vector<int>> up(n + 1, vector<int>(20, 0));
  32.     vector<vector<int>> cost(n + 1, vector<int>(20, 0));
  33.  
  34.     for (int k = 0; k < K - 1; k++) {
  35.         int nxt_s = start_blk[k+1];
  36.         int nxt_e = end_blk[k+1];
  37.         int max_nxt = p[nxt_s];
  38.         int min_prev = p[end_blk[k]];
  39.  
  40.         for (int j = start_blk[k]; j <= end_blk[k]; j++) {
  41.             int v = p[j];
  42.             if (max_nxt > v) {
  43.                 cost[j][0] = 1;
  44.                 int low = nxt_s, high = nxt_e, ans = -1;
  45.                 while (low <= high) {
  46.                     int mid = low + (high - low) / 2;
  47.                     if (p[mid] > v) {
  48.                         ans = mid;
  49.                         low = mid + 1;
  50.                     } else {
  51.                         high = mid - 1;
  52.                     }
  53.                 }
  54.                 up[j][0] = ans;
  55.             } else {
  56.                 cost[j][0] = 2;
  57.                 int low = nxt_s, high = nxt_e, ans = -1;
  58.                 while (low <= high) {
  59.                     int mid = low + (high - low) / 2;
  60.                     if (p[mid] > min_prev) {
  61.                         ans = mid;
  62.                         low = mid + 1;
  63.                     } else {
  64.                         high = mid - 1;
  65.                     }
  66.                 }
  67.                 up[j][0] = ans;
  68.             }
  69.         }
  70.     }
  71.  
  72.     for (int j = start_blk[K-1]; j <= end_blk[K-1]; j++) {
  73.         up[j][0] = j; 
  74.         cost[j][0] = 0;
  75.     }
  76.  
  77.     for (int step = 1; step < 20; step++) {
  78.         for (int j = 1; j <= n; j++) {
  79.             up[j][step] = up[up[j][step-1]][step-1];
  80.             cost[j][step] = cost[j][step-1] + cost[up[j][step-1]][step-1];
  81.         }
  82.     }
  83.  
  84.     vector<int> pref_inc(n + 1, 0);
  85.     for (int j = 1; j < n; j++) {
  86.         pref_inc[j] = pref_inc[j-1] + (p[j] < p[j+1] ? 1 : 0);
  87.     }
  88.     pref_inc[n] = pref_inc[n-1];
  89.  
  90.     vector<int> next_inc(n + 2, n + 1);
  91.     for (int j = n - 1; j >= 1; j--) {
  92.         if (p[j] < p[j+1]) {
  93.             next_inc[j] = j;
  94.         } else {
  95.             next_inc[j] = next_inc[j+1];
  96.         }
  97.     }
  98.  
  99.     for (int idx = 0; idx < q; idx++) {
  100.         int l, r;
  101.         cin >> l >> r;
  102.         if (l == r) {
  103.             cout << 1 << "\n";
  104.             continue;
  105.         }
  106.  
  107.         int M = pref_inc[r-1] - pref_inc[l-1];
  108.         if (M == 0) {
  109.             cout << 1 << "\n";
  110.             continue;
  111.         }
  112.  
  113.         int u = next_inc[l];
  114.         long long ans_jumps = 0;
  115.         int jumps_needed = M;
  116.         for (int step = 19; step >= 0; step--) {
  117.             if (jumps_needed >= (1 << step)) {
  118.                 ans_jumps += cost[u][step];
  119.                 u = up[u][step];
  120.                 jumps_needed -= (1 << step);
  121.             }
  122.         }
  123.         cout << 1 + ans_jumps << "\n";
  124.     }
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
12 8
8 3 5 7 9 6 11 1 10 4 12 2
3 4
10 11
5 8
3 8
4 10
2 10
5 7
1 8
stdout
copy 
2
2
2
4
5
7
2
5
https://ideone.com/Vx7Vrm
language:
C++14 (gcc 8.3)
created:
1 day 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!