fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int query(int node,int start,int end,int ar[],int tree[],int l,int r){
  5. 	if(start>r||end<l)
  6. 		return 0;
  7. 	if(start>=l&&end<=r)
  8. 		return tree[node];
  9. 	int mid=(start+end)/2;
  10. 	return max(query(2*node,start,mid,ar,tree,l,r),query(2*node+1,mid+1,end,ar,tree,l,r));
  11. }
  12. void update(int node,int start,int end,int ar[],int tree[],int ind,int val){
  13. 	if(start==end){
  14. 		tree[node]=val;
  15. 		ar[ind]=val;
  16. 		return;
  17. 	}
  18. 	int mid=(start+end)/2;
  19. 	if(ind<=mid)
  20. 		update(2*node,start,mid,ar,tree,ind,val);
  21. 	else
  22. 		update(2*node+1,mid+1,end,ar,tree,ind,val);
  23. 	tree[node]=max(tree[2*node],tree[2*node+1]);
  24. }
  25. int solve(){
  26. 	int n,L;
  27. 	cin>>n;
  28. 	pair<int,int>arr[n];
  29. 	for(int i=0;i<n;i++){
  30. 		int x;
  31. 		cin>>x;
  32. 		arr[i]={x,i+1};
  33. 	}
  34. 	cin>>L;
  35. 	if(L>n||L<=0)
  36. 		return -1;
  37. 	sort(arr,arr+n);
  38. 	int ar[n+1],tree[4*(n+1)+1];
  39. 	memset(ar,0,sizeof(ar));
  40. 	memset(tree,0,sizeof(tree));
  41. 	int ans=INT_MAX;
  42. 	for(auto it:arr){
  43. 		int temp=query(1,1,n,ar,tree,1,it.second-1);
  44. 		update(1,1,n,ar,tree,it.second,temp+1);
  45. 		if(ar[it.second]>=L)
  46. 			ans=min(ans,it.first);
  47. 	}
  48. 	if(ans==INT_MAX)
  49. 		ans=-1;
  50. 	return ans;
  51. }
  52. signed main(){
  53. 	ios_base::sync_with_stdio(false);
  54. 	cin.tie(0),cout.tie(0);
  55. 	int t;
  56. 	cin>>t;
  57. 	while(t--){
  58. 		cout<<solve()<<'\n';
  59. 	}
  60. }
Success #stdin #stdout 0s 4320KB
comments (?)
stdin
copy 
1
7
9 7 2 5 4 11 12 
3
stdout
copy 
11
https://ideone.com/wXBtMk
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!