fork download
copy 
  1. // Complexity    O(log(n)*log(m))
  2.  
  3.  
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define f(i,x,y) for(int i = (x);i < (y);++i)
  7. #define F(i,x,y) for(int i = (x);i > (y);--i)
  8. int max(int a,int b){return (a > b?a:b);}
  9. int min(int a,int b){return (a < b?a:b);}
  10. int mod(int a){return (a > 0?a:((-1)*(a)));}
  11.  
  12.  
  13. int indLess(int *arr,int sz,int val)// Assuming arr is sorted
  14. {
  15.   if(arr[0] >= val)return (-1+1);
  16.   else
  17.   {
  18.     int s = 0,e = sz-1;
  19.     while((e-s)>1)
  20.     {
  21.       int m = (s+e)/2;
  22.       if(arr[m] < val){s = m;}
  23.       else if(arr[m] > val){e = m-1;}
  24.       else{;}
  25.     }
  26.     if(arr[e] < val)return e+1;
  27.     else return s+1;
  28.   }
  29. }
  30.  
  31. int check(int *arr1,int *arr2,int sz1,int sz2,int k)
  32. {
  33.   int val0 = indLess(arr1,sz1,arr2[0])+0+1;
  34.   if(val0 > k)return -1;
  35.   else
  36.   {
  37.     int s = 0,e = sz2-1;
  38.     while((e-s)> 1)
  39.     {
  40.       int m = (e+s)/2;
  41.       int valm = indLess(arr1,sz1,arr2[m])+m+1;
  42.       if(valm == k){return (m);}
  43.       else if(valm > k){e = m-1;}
  44.       else {s = m;}
  45.     }
  46.     int vale = indLess(arr1,sz1,arr2[e])+e+1;
  47.     if(vale <= k){return e;}
  48.     else {return s;}
  49.   }
  50. }
  51.  
  52.  
  53. int func(int *arr1,int *arr2,int sz1,int sz2,int k)
  54. {
  55.   int *m;int ms;
  56.   int *M;int Ms;
  57.   if(arr1[sz1-1] >= arr2[sz2-1]){m = arr2,M = arr1;ms = sz2;Ms = sz1;}
  58.   else {m = arr1,M = arr2;ms = sz1;Ms = sz2;}
  59.   if(m[ms-1] <= M[0])
  60.   {
  61.     if(k <= ms)return m[k-1];
  62.     else return M[k-ms-1];
  63.   }
  64.   else//m[k-1] > M[0]
  65.   {
  66.     int p = check(m,M,ms,Ms,k);//return index
  67.     int a = indLess(m,ms,M[p]);// return num
  68.     int b = (k-(a+p+1));
  69.     if(b == 0)return M[p];
  70.     else return (m[a+b-1]);
  71.   }
  72. }
  73.  
  74.  
  75.  
  76.  
  77. int main()
  78. {
  79.   int n,m,k;
  80.   cin >> n >> m >> k;
  81.   int arr1[n];
  82.   int arr2[m];
  83.   f(i,0,n)
  84.     cin >> arr1[i];
  85.     f(i,0,m)
  86.     cin >> arr2[i];
  87.   cout << func(arr1,arr2,n,m,k) << endl;
  88.   return 0;
  89. }
  90.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
5
4
1 5 8 9 10
2 3 4 6 7
stdout
copy 
4
https://ideone.com/OMA08E
language:
C++ (gcc 8.3)
created:
7 years 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!