#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
int mid = l + (r - l) / 2;
if (r >= l)
{
// If the element is present at the middle
// itself
if (arr[mid] <= x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return mid;
}
int main()
{
int r = 0;
int n, m;
cin >> n >> m;
int *a = new int[n + m];
int *k = new int[m];
int p = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> k[i];
}
int index;
while (p < m)
{
if (k[p] >= a[n + p - 1])
{
a[n + p] = k[p];
p++;
}
else
{
index = binarySearch(a, 0, n + m, k[p]);
while (a[index] <= k[p])
{
index++;
}
r++;
swap(k[p], a[index]);
}
}
cout << r << endl;
return 0;
}
Copy