Advertisement
Gosunov

Untitled

Nov 9th, 2022
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4.  
  5. const int maxn = 200500;
  6. int a[maxn];
  7. int b[maxn];
  8. bool used[maxn];
  9.  
  10. int n, m;
  11.  
  12. int t[maxn];
  13.  
  14. int get(int i) {
  15.     int res = 0;
  16.     for (; i >= 0; i &= i + 1, --i) {
  17.         res += t[i];
  18.     }
  19.     return res;
  20. }
  21.  
  22. void upd(int i) {
  23.     for (; i < m; i |= i + 1) {
  24.         t[i] += 1;
  25.     }
  26. }
  27.  
  28. void solve() {
  29.     cin >> n;
  30.     for (int i = 0; i < n; ++i) {
  31.         cin >> a[i];
  32.     }
  33.     cin >> m;
  34.     for (int i = 0; i < m; ++i) {
  35.         cin >> b[i];
  36.     }
  37.     sort(b, b + m);
  38.     for (int i = 0; i < n; ++i) {
  39.         int idx = lower_bound(b, b + m, a[i]) - b;
  40.  
  41.         int l = idx - 1;
  42.         int r = m;
  43.         while (r - l > 1) {
  44.             int mid = (l + r) / 2;
  45.             int s = get(mid) - get(idx - 1);
  46.             int d = mid - idx + 1;
  47.             if (s == d) {
  48.                 l = mid;
  49.             } else {
  50.                 r = mid;
  51.             }
  52.         }
  53.         if (r == m) {
  54.             cout << i << '\n';
  55.             return;
  56.         }
  57.         upd(r);
  58.     }
  59.     cout << m << '\n';
  60. }
  61.  
  62. signed main() {
  63.     ios::sync_with_stdio(0); cin.tie(0);
  64.     solve();
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement