Auringonlasku

#include <bits/stdc++.h>
#include <stdint.h>
using namespace std;

uint32_t n,q;
uint32_t t[100000];

uint32_t puu[1<<18];
uint32_t size;
bool e[500000];

void muuta(uint32_t index, uint32_t val){
  puu[index] = val;
  for(index /= 2; index > 0; index/=2){
    puu[index] = max(puu[index*2],puu[index*2+1]);
  }
}

uint32_t isompi(uint32_t index){
  uint32_t val = puu[index];
  index++;
  while(index > 0){
    if(puu[index] > val){
      while(index < (size/2)){
	if(puu[index*2] > val){
	  index *= 2;
	}
	else{
	  index *= 2;
	  index++;
	}
      }
      break;
    }
    else{
      if(e[index]){
	return size;
      }
      if(index %2 == 1){
	index++;
      }
      else{
	index /= 2;
      }
    }
  }
  return index;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
   size = 1;
  while(size < n){
    size *= 2;
  }
  size *= 2;
  for(uint32_t i=0; i<size; i++){
    e[i] = 0;
  }
   for(uint32_t i=2; i<size; i*=2){
    e[i-1] = 1;
  }
 
  for(uint32_t i=0; i<size; i++){
    puu[i] = 0;
  }
  for(uint32_t i=0; i<n; i++){
    cin >> t[i];
    muuta(i+size/2,t[i]);
  }
  for(uint32_t i=0; i<q; i++){
    uint32_t a,b;
    cin >> a >> b;
    uint32_t ans = 1;
    uint32_t w = isompi(a-1+size/2);
    while((w <= (b-1+size/2))){
      // cout << w << " " ;
      ans++;
      w = isompi(w);
    }
    //  cout << "\n";
    cout << ans << "\n";
  }
  
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: WRONG ANSWER

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

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

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

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: ACCEPTED