题解 | 动态整数集最近值提取

#include <bits/stdc++.h>
using ll = long long ; 
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define vii vector<vector<ll>>
#define fi first 
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); i++)
const ll inf = 2e18 + 9 ;
const ll mod1 = 1e9 + 7 ; 
const ll mod2 = 998244353 ; 
typedef pair<int, int> pll;
typedef long double db;
inline ll comb(int n, int k){if (k < 0 || k > n)return 0;if (k == 0 || k == n)return 1;k = min(k, n - k);ll numerator = 1;  ll denominator = 1; for (int i = 1; i <= k; ++i){numerator *= (n - k + i);denominator *= i;ll g = __gcd(numerator, denominator);numerator /= g;denominator /= g;}return numerator / denominator;}
void init()
{

}
inline ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;};
inline int read(){int x = 0;short f = 1;char c = getchar();while ((c < '0' || c > '9') && c != '-')c = getchar();if (c == '-')f = -1, c = getchar();while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();x *= f;return x;}
inline ll qsm(ll a , ll b){ll res = 1 ; while(b){if(b & 1){res *= a ; }b >>= 1 ; a *= a ; }return res ; }
int dir[4][2] = {{1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}};
int dirx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
int diry[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void work() 
{
    int q ; cin >> q ; 
    multiset<int>k ; 
    while(q--)
    {
        int op , x ; cin >> op >> x ; 
        if(op == 1)
        {
            if(k.count(x) == 0)
            {
                k.emplace(x) ; 
            }
            else    
            {
                cout << "Already Exist" << endl ; 
            }
        }
        else 
        {
            if(k.empty())
            {
                cout << "Empty" << endl ; 
                continue ; 
            }
            auto it = k.lower_bound(x) ; 
            if(*it != x)
            {
                if(it == k.begin())
                {
                    cout << *it << endl ; 
                    k.erase(it) ;
                    continue ; 
                }
                int a1 = *it ; 
                it-- ; 
                int a2 = *it ; 
                if(abs(a2 - x) <= abs(a1 - x))
                {
                    cout << *it << endl ; 
                    k.erase(it) ; 
                }
                else 
                {
                    it++ ; 
                    cout << *it << endl ; 
                    k.erase(it) ; 
                }
            }
            else 
            {
                cout << *it << endl ; 
                k.erase(it) ; 
            }
        }
    }
}
signed main() 
{
    init() ;
    ios ; 
    int t = 1;
    while (t--) 
    {
        work();
    }
    return 0;
}