Sunset

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream fin("AAtest.in.txt");
ll n,q,mit[100005],c,k,x,y,koht,ma;
pair<ll,ll> p[100005];
vector<ll> t;

bool boo(pair<ll,ll> e,pair<ll,ll> v){
    if(v.first!=e.first) return e.first>v.first;
    return e.second<v.second;
}

void pane(ll n,ll x,ll y,ll i,ll j,ll v){
    if(x>y || j<x || y<i) return ;
    if(x==y){
        t[n]=v;
        return ;
    }
    pane(2*n,x,(x+y)/2,i,j,v);
    pane(2*n+1,(x+y)/2+1,y,i,j,v);
    t[n]=t[2*n]+t[2*n+1];
}

ll otsi(ll n,ll x,ll y,ll i){ //cout<<n<<" "<<x<<" "<<y<<" "<<c/2<<"\n";
    if(x>y || y<=i) return 0;
    if(!t[n]) return 0;
    if(x==y) return n-c/2+1;
    ll l=otsi(2*n,x,(x+y)/2,i);
    if(l==0) l=otsi(2*n+1,(x+y)/2+1,y,i);
    return l;
}

void vaar(ll n,ll x,ll y,ll i,ll j){
    if(x>y || j<x || y<i) return ;
    if(x==y){
        if(t[n]>ma){
            ma=t[n];
            koht=n-c/2+1;
        }
        return ;
    }
    if(x>=i && j>=y) if(t[n]>ma){
        vaar(2*n,x,(x+y)/2,i,j);
        vaar(2*n+1,(x+y)/2+1,y,i,j);
    }
    if(t[2*n]>ma) vaar(2*n,x,(x+y)/2,i,j);
    if(t[2*n+1]>ma) vaar(2*n+1,(x+y)/2+1,y,i,j);
}

void pane2(ll n,ll x,ll y,ll i,ll j,ll v){
    if(x>y || i>y || j<x) return ;
    if(x==y){
        t[n]=v;
        return;
    }
    pane2(2*n,x,(x+y)/2,i,j,v);
    pane2(2*n+1,(x+y)/2+1,y,i,j,v);
    t[n]=max(t[2*n],t[2*n+1]);
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    c=1;
    while(c<n) c*=2;
    c*=2;
    t.resize(c+3);
    for(int i=1; i<=n; i++) cin>>p[i].first,p[i].second=i;
    sort(p,p+n+1,boo);
    memset(mit,-1,sizeof(mit));
    for(int i=0; i<n; i++){
        pane(1,1,c/2,p[i].second,p[i].second,1);
        k=otsi(1,1,c/2,p[i].second);
        mit[p[i].second]=mit[k]+1;
    }
    t.resize(0);
    t.resize(c+3,0);
    for(int i=0; i<n; i++) pane2(1,1,c/2,p[i].second,p[i].second,p[i].first);
    for(int i=0; i<q; i++){
        cin>>x>>y;
        ma=0;
        vaar(1,1,c/2,x,y);
        //cout<<koht<<"\n";
        cout<<mit[x]-mit[koht]+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: 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: 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: 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: TIME LIMIT EXCEEDED

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: ACCEPTED