Sunset

input/code.cpp: In function 'int main()':
input/code.cpp:89:7: warning: unused variable 'f' [-Wunused-variable]
   int f=leiap(1,1,c,a,b);
       ^
input/code.cpp: In function 'int leiap(int, int, int, int, int)':
input/code.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

#include <bits/stdc++.h>
#include <bits/stdc++.h>
#define mis(x) cout << #x <<" = " <<x<<endl
#define rep(i, a, b) for(int i=(a);(i)<(b);(i)++)
#define re(i,a) rep((i),0,(a))
using namespace std;
typedef long long ll;
ifstream fin("AAtest.in.txt");
int const cc=1000001;
int n,l,c,k,a,b,q,ma,koht;
ll h,g;
vector<pair<ll,int> > p;
vector<int> m,pai,t;

void loe(){
	cin>>n>>q;
	re(i,n){
		cin>>h;
		p.push_back({h,i});
	}
	sort(p.begin(),p.end());
	m.resize(n);
	g=p[0].first;	l=1;
	re(i,n){
		if(i and g<p[i].first){
			g=p[i].first;
			l++;
		}
		m[p[i].second]=l;
	}
//	for(auto i:m)cout<<i<<" ";cout<<endl;
}

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

int leia(int n,int x,int y,int i,int j){
	if(j<x or y<i)return cc;
	if(i<=x and y<=j)return t[n];
	return(min(leia(n*2,x,(x+y)/2,i,j),leia(n*2+1,(x+y)/2+1,y,i,j)));
}

void pik(int n,int x,int y,int i,int v){
	if(i<x or y<i)return;
	if(x==y){//cout<<n<<" "<<i<<" "<<v<<endl;
		t[n]=v;
		return;
	}
	pik(n*2,x,(x+y)/2,i,v);
	pik(n*2+1,(x+y)/2+1,y,i,v);
	t[n]=max(t[n*2],t[n*2+1]);
}

int leiap(int n,int x,int y,int i,int j){//cout<<x<<" "<<y<<" "<<i<<" "<<j<<" "<<ma<<endl;
	if(j<x or y<i)return -1;
	if(x==y){//cout<<x;
		koht=n-c;
		return t[n];
	}
	if(t[n*2]>ma)ma=max(ma,leiap(n*2,x,(x+y)/2,i,j));
	if(t[n*2+1]>ma)ma=max(ma,leiap(n*2+1,(x+y)/2+1,y,i,j));
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);	cout.tie(0);cerr.tie(0);
	loe();
	c=1;while(c<=l)c<<=1;t.resize(2*c+5,cc);
	pai.resize(n,0);
	for(int i=n-1;i>=0;i--){
		k=cc;
		pane(1,1,c,m[i],i);
		if(m[i]<l) k=leia(1,1,c,m[i]+1,l);
		if(k<cc)	pai[i]=pai[k]+1;
	}
	//for(auto i:pai)cout<<i<<" ";cout<<endl;
	c=1;while(c<=n)c<<=1;//mis(c);
	t.resize(2*c+5);
	re(i,2*c+5)t[i]=-1;
	re(i,n)	pik(1,1,c,i+1,m[i]);
//	for(auto i:t)cout<<i<<" ";cout<<endl;
	re(i,q){
		cin>>a>>b;
		ma=0;koht=0;
		int f=leiap(1,1,c,a,b);
		int vas=pai[a-1]-pai[koht]+1;
//		mis(koht);
//		mis(f);
		cout<<vas<<"\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: WRONG ANSWER

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: WRONG ANSWER

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: WRONG ANSWER

Test 13

Group: 1

Verdict: WRONG ANSWER

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: WRONG ANSWER

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: WRONG ANSWER

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: WRONG ANSWER

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: WRONG ANSWER

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: WRONG ANSWER

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: WRONG ANSWER

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: WRONG ANSWER

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: WRONG ANSWER

Test 34

Group: 3

Verdict: WRONG ANSWER

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: WRONG ANSWER

Test 37

Group: 3

Verdict: WRONG ANSWER

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: WRONG ANSWER

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: WRONG ANSWER

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: WRONG ANSWER

Test 51

Group: 3

Verdict: WRONG ANSWER

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: ACCEPTED