Sum

#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 <= 250)
      {
          tempo++;
          LL t = nxt[cur];
          target[i0].push_back(t);
          cur = t;
          if(cur == INF)break;
      }
  }

  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

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER