Sunset

input/code.cpp: In function 'int main()':
input/code.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &Q);
   ~~~~~^~~~~~~~~~~~~~~~
input/code.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &H[i]);
     ~~~~~^~~~~~~~~~~~~
input/code.cpp:59:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int l, r; scanf("%d%d", &l, &r);
               ~~~~~^~~~~~~~~~~~~~~~

#include<bits/stdc++.h>

using namespace std;
using lint = long long;

int N, Q;
int H[int(1.1e5)];
int A[int(1.1e5)], M;

const int LEAF = 1<<18;
int tree[LEAF+LEAF];

void upd(int x, int v) {
  tree[x += LEAF] = v;
  while(x >>= 1) tree[x] = min(tree[x+x], tree[x+x+1]);
}

int get(int l, int r) {
  l += LEAF; r += LEAF;
  int ret = N+1;
  while(l <= r) {
    if( l & 1) ret = min(ret, tree[l]);
    if(~r & 1) ret = min(ret, tree[r]);
    l = (l+1) >> 1;
    r = (r-1) >> 1;
  }
  return ret;
}

int par[18][int(1.1e5)];

int main() {
  scanf("%d%d", &N, &Q);
  for(int i = 1; i <= N; i++) {
    scanf("%d", &H[i]);
    A[i] = H[i];
  }
  sort(A+1, A+N+1);
  M = distance(A, unique(A+1, A+N+1));
  for(int i = 1; i <= N; i++) {
    H[i] = distance(A, lower_bound(A+1, A+M+1, H[i]));
  }

  fill(tree, tree+LEAF+LEAF, N+1);
  
  for(int i = N; i > 0; i--) {
    par[0][i] = get(H[i]+1, M+1);
    upd(H[i], i);
  }
  
  par[0][N+1] = N+1;
  for(int k = 1; k < 18; k++) {
    for(int i = 1; i <= N+1; i++) {
      par[k][i] = par[k-1][par[k-1][i]];
    }
  }

  for(int q = 0; q < Q; q++) {
    int l, r; scanf("%d%d", &l, &r);
    int ans = 1;
    l = par[0][l];
    for(int k = 17; k >= 0; k--) {
      //printf("%d %d %d\n", k, l, par[k][l]);
      if(par[k][l] <= r) {
        ans += 1<<k;
        l = par[k][l];
      }
    }
    if(l <= r) {
      ans += 1;
    }
    printf("%d\n", ans);
  }

  
  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: ACCEPTED

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: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

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: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED