fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, q, l[20][200001], r[20][200001], nxt[20][200001], res;
  5. vector<int> v, H;
  6.  
  7. void init()
  8. {
  9.     for (int i = 0; i < 20; ++i)
  10.     {
  11.         fill_n(l[i], N + 1, N);
  12.         fill_n(r[i], N + 1, N);
  13.         fill_n(nxt[i], N + 1, N);
  14.     }
  15.     H.push_back(0);
  16.     v.clear();
  17.     for (int i = 0; i < N; ++i)
  18.     {
  19.         while (!v.empty() && H[v.back()] <= H[i])
  20.         {
  21.             v.pop_back();
  22.         }
  23.         l[0][i] = (v.empty() ? N : v.back());
  24.         v.push_back(i);
  25.     }
  26.     v.clear();
  27.     for (int i = N - 1; i >= 0; --i)
  28.     {
  29.         while (!v.empty() && H[v.back()] <= H[i])
  30.         {
  31.             v.pop_back();
  32.         }
  33.         r[0][i] = (v.empty() ? N : v.back());
  34.         v.push_back(i);
  35.     }
  36.     for (int i = 0; i < N; ++i)
  37.     {
  38.         nxt[0][i] = (H[l[0][i]] > H[r[0][i]] ? l[0][i] : r[0][i]);
  39.     }
  40.     for (int i = 1; i < 20; ++i)
  41.     {
  42.         for (int j = 0; j < N; ++j)
  43.         {
  44.             l[i][j] = l[i - 1][l[i - 1][j]];
  45.             r[i][j] = r[i - 1][r[i - 1][j]];
  46.             nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
  47.         }
  48.     }
  49. }
  50.  
  51. int minimum_jumps(int A, int B, int C, int D)
  52. {
  53.     res = 0;
  54.     for (int i = 19; i >= 0; --i)
  55.     {
  56.         if (A <= l[i][B] && r[0][l[i][B]] <= D)
  57.         {
  58.             B = l[i][B];
  59.         }
  60.     }
  61.     if (C <= r[0][B] && r[0][B] <= D)
  62.     {
  63.         return 1;
  64.     }
  65.     for (int i = 19; i >= 0; --i)
  66.     {
  67.         if (r[0][nxt[i][B]] < C)
  68.         {
  69.             B = nxt[i][B];
  70.             res += (1 << i);
  71.         }
  72.     }
  73.     if (r[0][nxt[0][B]] <= D)
  74.     {
  75.         return res + 2;
  76.     }
  77.     for (int i = 19; i >= 0; --i)
  78.     {
  79.         if (r[i][B] < C)
  80.         {
  81.             B = r[i][B];
  82.             res += (1 << i);
  83.         }
  84.     }
  85.     return (C <= r[0][B] && r[0][B] <= D ? res + 1 : -1);
  86. }
  87.  
  88. signed main()
  89. {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0);
  93.     cin>>N>>q;
  94.     for (int i = 0; i < N; i++) 
  95.     {
  96.         int d; cin>>d;
  97.         H.push_back(d);
  98.     }
  99.     init();
  100.     while (q--)
  101.     {
  102.         int a, b, c, d;
  103.         cin>>a>>b>>c>>d;
  104.         cout<<minimum_jumps(a, b, c, d)<<'\n';
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 46672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/58jdLy
language:
C++14 (gcc 8.3)
created:
4 days 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!