hacker rank sorted segment trees

#include<bits/stdc++.h>
#define X first
#define Y second
#define For(i,a,b) for(int i=a; i<=b; i++)
#define Ford(i,a,b) for(int i=a; i>=b; i--)
#define assign(fi,fo) {freopen(fi,"r",stdin); freopen(fo,"w",stdout);}
using namespace std;
const int sz=75000;
int n, Q, k, Count, ii;
int z[sz+1], a[sz+1], b[sz+1];
int f[(sz+1)*8],cnt[(sz+1)*8];
pair<int, int>q[sz+1];
void gen(int node, int l, int r){
	if(l==r)cnt[node]=b[l]; else{
		gen(node*2,l,(l+r)/2);
		gen(node*2+1,(l+r)/2+1,r);
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
}
void search(int node, int l, int r, int L, int R){
	if(f[node]!=-1){
		cnt[node]=f[node];
		if(f[node])f[node*2]=(l+r)/2-l+1; else f[node*2]=0;
		if(f[node])f[node*2+1]=r-(l+r)/2; else f[node*2+1]=0;
		f[node]=-1;
	}
	if(l>R||r<L)return; else
	if(L<=l&&r<=R){
		Count+=cnt[node];
		//cout<<"This is "<<node<<" "<<cnt[node]<<"\n";
	}else{
		search(node*2,l,(l+r)/2,L,R);
		search(node*2+1,(l+r)/2+1,r,L,R);
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
}
void build(int node, int l, int r, int L, int R){
	if(f[node]!=-1){
		cnt[node]=f[node];
		if(f[node])f[node*2]=(l+r)/2-l+1; else f[node*2]=0;
		if(f[node])f[node*2+1]=r-(l+r)/2; else f[node*2+1]=0;
		f[node]=-1;
	}
	if(l>R||r<L)return; else
	if(L<=l&&r<=R){
		cnt[node]=r-l+1;
		f[node*2]=(l+r)/2-l+1;
		f[node*2+1]=r-(l+r)/2;
		//cout<<"      _ "<<node<<endl;
	}else{
		build(node*2,l,(l+r)/2,L,R);
		build(node*2+1,(l+r)/2+1,r,L,R);
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
}
void build1(int node, int l, int r, int L, int R){
	if(f[node]!=-1){
		cnt[node]=f[node];
		if(f[node])f[node*2]=(l+r)/2-l+1; else f[node*2]=0;
		if(f[node])f[node*2+1]=r-(l+r)/2; else f[node*2+1]=0;
		f[node]=-1;
	}
	if(l>R||r<L)return; else
	if(L<=l&&r<=R){
		cnt[node]=0;
		f[node*2]=0;
		f[node*2+1]=0;
		//cout<<"         "<<node<<endl;
	}else{
		build1(node*2,l,(l+r)/2,L,R);
		build1(node*2+1,(l+r)/2+1,r,L,R);
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
}
void find(int node, int l, int r){
	if(f[node]!=-1){
		cnt[node]=f[node];
		if(f[node])f[node*2]=(l+r)/2-l+1; else f[node*2]=0;
		if(f[node])f[node*2+1]=r-(l+r)/2; else f[node*2+1]=0;
		f[node]=-1;
	}
	if(l==r){
		if(l==k)ii=cnt[node];
	}else{
		find(node*2,l,(l+r)/2);
		find(node*2+1,(l+r)/2+1,r);
	}
}

void Solve(const int pos){
	int x=z[pos]; //cout<<" "<<z[pos]<<endl;
	memset(f,-1,sizeof(f));
	For(i,1,n)if(a[i]>x)b[i]=0;else b[i]=1;
	gen(1,1,n);
	For(i,1,Q){
		Count=0;
		search(1,1,n,q[i].X,q[i].Y);
		build(1,1,n,q[i].X,q[i].X+Count-1);
		build1(1,1,n,q[i].X+Count,q[i].Y);
		//printf("%d %d %d\n",q[i].X,q[i].Y,Count);
	}
	find(1,1,n);
}
int main(){
	assign("inp.inp","out.out");
	scanf("%d%d%d",&n,&Q,&k); k++;
	For(i,1,n){
		scanf("%d",&z[i]);
		a[i]=z[i];
	}
	For(i,1,Q){
		scanf("%d%d",&q[i].X,&q[i].Y);
		q[i].X++; q[i].Y++;
	}
	sort(z+1,z+1+n);
	int res, l=1, r=n, mid;
	while(l<=r){
		mid=(l+r)/2;
		Solve(mid);
		if(ii){
			res=mid; //cout<<"find\n";
			r=mid-1;
		}else l=mid+1;
		//return 0;
	}
	cout<<z[res]<<endl;
	return 0;
}