Auringonlasku

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0);

typedef long long ll;
using namespace std;

#define N (1<<17)
#define INF 2147483647

int n, q;
int t[2*N];

int get_max(int a, int b) {
  a += N; b += N;
  int res = -2147483647;
  while (a <= b) {
    if (a % 2 == 1) res = max(res, t[a++]);
    if (b % 2 == 0) res = max(res, t[b--]);
    a /= 2; b /= 2;
  }
  return res;
}

int find_max_index(int a, int b) {
  if (a > b) return 0;
  if (a == b) return a;
  if (a == b+1) {
    if (t[b] > t[a]) return b;
    else return a;
  }
  int mid = (a+b)/2;
  int mx = get_max(a,b);
  if (get_max(a, mid) == mx) return find_max_index(a, mid);
  else return find_max_index(mid+1, b);
}

void Set(int k, int x) {
  k += N;
  t[k] = x;
  for (k /= 2; k >= 1; k /= 2) {
    t[k] = max(t[2*k], t[2*k+1]);
  }
}

int ansQuery(int a, int b) {
  if (a > b) return 0;
  int mx_idx = find_max_index(a,b);
  return 1 + ansQuery(a, mx_idx-1);
}

int main() {
  IO; cin>>n>>q;
  
  FOR(i,n,N) {
    t[i+N] = -INF; 
  }
  FOR(i,0,n) {
    int x; cin>>x;
    Set(i, x);
  }
  
  
  
  FOR(i,0,q) {
    int a,b; cin>>a>>b;
    cout<<ansQuery(a-1,b-1)<<"\n";
  }
  
  
}

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: TIME LIMIT EXCEEDED

Test 11

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 51

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: TIME LIMIT EXCEEDED