Sunset

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>


using namespace std;

typedef long long LL;

const LL MAX = 200005;
const LL INF = (1000 * 1000 * 1000) + 50;

LL n, q;
LL h[MAX] = {}, nxt[MAX] = {};
vector<LL> target[MAX] = {};

LL b_Search(LL pos, LL x)
{
    LL answer = -1;
    LL lo = 0;
    LL hi = target[pos].size()-1;
    while(lo <= hi)
    {
        LL mid = lo + (hi-lo)/2;
        if(target[pos][mid] <= x)
        {
            answer = max(answer, mid);
            lo = mid+1;
        }else hi = mid-1;
    }
    return answer + 1;
}


int main(void)
{
  cin >> n >> q;
  for(LL i0 = 0; i0 < n; i0++)cin >> h[i0];

  stack<pair<LL, LL> > st;
  st.push(make_pair(0, h[0]));
  for(LL i0 = 1; i0 < n; i0++)
  {
      while(!st.empty() && st.top().second < h[i0])
      {
          nxt[st.top().first] = i0;
          st.pop();
      }
      st.push(make_pair(i0, h[i0]));
  }
  while(!st.empty() )
  {
      nxt[st.top().first] = INF;
      st.pop();
  }

  for(LL i0 = 0; i0 < n; i0++)
  {
      LL cur = i0;
      LL tempo = 0;
      while(tempo * tempo <= 400)
      {
          tempo++;
          LL t = nxt[cur];
          target[i0].push_back(t);
          cur = t;
          if(cur == INF)break;
      }
  }

  /****
  for(LL i0 = 0; i0 < n; i0++)
  {
      LL num_Bro = target[i0].size();
      for(LL j0 = 0; j0 < num_Bro; j0++)
      {
          cout << target[i0][j0] << " ";
      }
      cout << endl;
  }
  ****/

  for(LL i0 = 0; i0 < q; i0++)
  {
      LL i, j, ans = 1;
      cin >> i >> j;
      i--;
      j--;
      while(i < j)
      {
          LL SIZE = target[i].size();
          LL last = target[i][SIZE-1];
          if(last != INF && last <= j)
          {
              ans += SIZE;
              i = last;
          }else
          {
              ans += b_Search(i, j);
              break;
          }
      }
      cout << ans << endl;
  }

  return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: ACCEPTED