OBST
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...