1354D - Multiset - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
#define vi vector <int>

const int N = 1e6+9 , INF = 1e9+9 , mod=1e9+7 , B=450 ;
int  fn[N];
void ADD(int ind , int val){
    for(int i=ind ; i<N ; i+= i & -i)fn[i]+=val;
}
int GET(int ind){
    int sum=0;
    for(int i=ind ; i>0 ; i-= i & -i){
        sum+=fn[i];
    }
    return sum;
}
int bs(int x){
    int l=0 , r=N , mid=(l+r)/2;
    while(r-l>1){
        if(GET(mid)<=x)l=mid;
        else r=mid;
        mid=(l+r)/2;
    }
    return l;
}

int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    int n , m;
    cin  >> n >> m;
    int mx=0;
    while(n--){
        int a;
        cin >> a;
        mx=max(mx , a);
        ADD(a+1 , 1);
    }
    while(m--){
        int q;
        cin >> q;
        if(q>0){
            ADD(q+1 , 1);
        }
        else{
            q=-(q+1);
            ADD(bs(q)+1 , -1);
        }
    }
    int ans=bs(0);
    cout << (ans>1000000 ? 0 : ans) << endl;

}