fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int lli;
  5. typedef pair<int,int> pii;
  6. typedef vector<int> vec;
  7.  
  8. #define pb push_back
  9. #define mp make_pair
  10. #define mt make_tuple
  11. #define scn(n) scanf("%d",&n)
  12. #define scnll(n) scanf("%lld",&n)
  13. #define scn2(n,m) scanf("%d%d",&n,&m)
  14. #define scn2ll(n,m) scanf("%lld%lld",&n,&m)
  15. #define atoz(v) v.begin(),v.end()
  16. #define fill(a,v) memset(a,v,sizeof(a))
  17. #define sz(v) v.size()
  18. #define fi first
  19. #define se second
  20. #define inf 1e9
  21. #define pi acos(-1.0)
  22. #define sqr(x) x*x
  23. #define max3(a,b,c) max(a,max(b,c))
  24. #define min3(a,b,c) min(a,min(b,c))
  25. #define N 100005
  26.  
  27. vector<int>tree[5*N];
  28. int a[N],n,q;
  29.  
  30. lli mx=-1e11;
  31. lli mn=1e11;
  32. map<int,int>idx;
  33.  
  34. /** http://w...content-available-to-author-only...j.com/problems/MKTHNUM/ **/
  35. /** see merge sort tree from codechef**/
  36.  
  37. void build_tree( int cur, int l, int r )
  38. {
  39.     if( l==r )
  40.     {
  41.         tree[cur].pb( a[l] );
  42.         return ;
  43.     }
  44.  
  45.     int mid = (r+l)/2;
  46.     int left = 2*cur;
  47.     int right =  2*cur+1;
  48.  
  49.     build_tree(left, l, mid );  // Build left tree
  50.     build_tree(right, mid+1, r );   // Build right tree
  51.  
  52.     int i=0,j=0;
  53.     int md=tree[left].size();
  54.     int hi=tree[right].size();
  55.  
  56.     /**merging two sorted vector**/
  57.  
  58.     for(int kk=0 ; kk<hi+md ; kk++)
  59.     {
  60.         if(i==md)tree[cur].pb(tree[right][j++]);
  61.  
  62.         else if(j==hi)tree[cur].pb(tree[left][i++]);
  63.  
  64.         else if(tree[left][i]<tree[right][j])tree[cur].pb(tree[left][i++]);
  65.  
  66.         else tree[cur].pb(tree[right][j++]);
  67.     }
  68. }
  69.  
  70. int query( int cur, int l, int r, int x, int y, int k)
  71. {
  72.     if( r < x || l > y )
  73.     {
  74.         return 0; //out of range
  75.     }
  76.     if( x<=l && r<=y )
  77.     {
  78.         //Binary search over the current sorted vector to find elements smaller than K
  79.         mx = max(mx,(lli)tree[cur][tree[cur].size()-1]);
  80.         mn = min(mn,(lli)tree[cur][0]);
  81.  
  82.         return upper_bound(atoz(tree[cur]),k)-tree[cur].begin();
  83.     }
  84.  
  85.     int mid=(r+l)/2;
  86.  
  87.     return query(2*cur,l,mid,x,y,k)+query(2*cur+1,mid+1,r,x,y,k);
  88. }
  89.  
  90. int main()
  91. {
  92.     scn2(n,q);
  93.  
  94.  
  95.     for(int i=1 ; i<=n; i++){
  96.         scn(a[i]);
  97.         idx[a[i]]=i;
  98.     }
  99.  
  100.  
  101.     build_tree(1,1,n);
  102.  
  103.     while(q--)
  104.     {
  105.  
  106.         int lo,hi,k;
  107.         scn2(lo,hi);
  108.         scn(k);         /** kth smallest element in this range*/
  109.  
  110.        // printf("oka-> %d\n",query(1,1,n,lo,hi,k));
  111.         int temp = query(1,1,n,lo,hi,k);
  112.         int l=(int)mn,h=(int)mx;
  113.         int mid;
  114.  
  115.          while(l<=h){
  116.  
  117.              mid = (l+h)/2;
  118.  
  119.              temp = query(1,1,n,lo,hi,mid);
  120.  
  121.              if(temp == k && (idx[mid]>=lo && idx[mid]<=hi)){
  122.                 printf("%d\n",mid);
  123.                 break;
  124.              }
  125.              else if(temp<k)l=mid+1;
  126.              else h=mid-1;
  127.          }
  128.     }
  129.  
  130.     return 0;
  131. }
  132.  
  133.  
Success #stdin #stdout 0.01s 15396KB
comments (?)
stdin
copy 
1 1
1 
1 1 1
stdout
copy 
1
https://ideone.com/5yUXuN
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

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!