OBST

 avatar
unknown
plain_text
2 years ago
2.2 kB
7
Indexable
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<int, int>  pii;

#define FastIO          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define FileIO          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define fi              first
#define se              second
#define max_heap(T)     priority_queue<T>
#define min_heap(T)     priority_queue<T, vector<T>, greater<T>>
#define fr(i, a, b)     for(int i=a;i<b;i++)
#define frr(i, a, b)    for(int i=a;i>b;i--)
#define frin(i, A)      for(auto &i : A)
#define sz(x)           (int)x.size()
#define all(A)          A.begin(), A.end()
#define mins(a, b)      a = min(a, b)
#define maxs(a, b)      a = max(a, b)
#define pb              push_back
#define popcnt          __builtin_popcount
#define setprec(x)      cout << fixed << setprecision(x)
#define md(a)           (a%MOD + MOD)%MOD

const ll  INF  = 2e9;
const ll  MOD  = 1e9 + 7;
const int MAXN = 2e5 + 5;

int q;
char tp;
int x, h;
set<pii> st;
set<pii>::iterator it1, it2;
set<int> built;

void solve() {
    cin >> q;
    while(q--) {
        cin >> tp;
        if(tp == '+') {
            cin >> x >> h;
            st.insert({x, h});
            built.insert(x);
            it1 = st.find({x, h});
            if(it1 != st.begin() && prev(it1)->se > it1->se)
                st.erase(it1);
            else
                while(it1 != st.end()) {
                    it2 = it1;
                    it2++;
                    if(it2 == st.end())
                        break;
                    if(it2->se < it1->se)
                        st.erase(it2);
                    else
                        break;
                }
        }
        else if(tp == '?') {
            cin >> x;
            if(built.find(x) == built.end())
                cout << "I'M SORRY TOQROL :(\n";
            else {
                it1 = st.lower_bound({x, 0});
                if(it1 == st.end() || it1->fi != x)
                    cout << "NO\n";
                else
                    cout << "YES\n";
            }
        }
    }
}

int32_t main() {
    FastIO
    int T;
    // cin >> T;
    T = 1;
    while(T--)
        solve();
    return 0;
}
Editor is loading...