Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(a) (a).begin(), (a).end()
- const int maxn = 200500;
- int a[maxn];
- int b[maxn];
- bool used[maxn];
- int n, m;
- int t[maxn];
- int get(int i) {
- int res = 0;
- for (; i >= 0; i &= i + 1, --i) {
- res += t[i];
- }
- return res;
- }
- void upd(int i) {
- for (; i < m; i |= i + 1) {
- t[i] += 1;
- }
- }
- void solve() {
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- cin >> m;
- for (int i = 0; i < m; ++i) {
- cin >> b[i];
- }
- sort(b, b + m);
- for (int i = 0; i < n; ++i) {
- int idx = lower_bound(b, b + m, a[i]) - b;
- int l = idx - 1;
- int r = m;
- while (r - l > 1) {
- int mid = (l + r) / 2;
- int s = get(mid) - get(idx - 1);
- int d = mid - idx + 1;
- if (s == d) {
- l = mid;
- } else {
- r = mid;
- }
- }
- if (r == m) {
- cout << i << '\n';
- return;
- }
- upd(r);
- }
- cout << m << '\n';
- }
- signed main() {
- ios::sync_with_stdio(0); cin.tie(0);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement