q.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <cmath>
#include <string>
#include <cstdlib>
#define f first
#define s second

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int MAXN = 2e5 + 10;
vector <int> t(4 * MAXN, -1);

void update(int v, int tl, int tr, int pos, int val){
    if (tl > tr){
        return;
    }
    if (tl == tr){
        t[v] = val;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm){
        update(v << 1, tl, tm, pos, val);
    }
    else{
        update((v << 1) | 1, tm + 1, tr, pos, val);
    }
    t[v] = max(t[v << 1], t[(v << 1) | 1]);
}

int get_max(int v, int tl, int tr, int l, int r){
    if (l > r)
        return -1;
    if (tl == l && tr == r){
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    return max(get_max(v << 1, tl, tm, l, min(r, tm)),
               get_max((v << 1) | 1, tm + 1, tr, max(tm + 1, l), r));
}
pair <string, pair <int, int> > q[MAXN];

int main() {
    IOS;
    int tt;
    cin >> tt;
    vector <pair <int, int> > vec;
    vec.push_back({0, 0});
    for (int i = 1; i <= tt; i++){
        cin >> q[i].f >> q[i].s.f >> q[i].s.s;
        if (q[i].f == "add"){
            vec.push_back(q[i].s);
        }
    }
    int m = vec.size();

    sort(vec.begin(), vec.end());

    for (int i = 1; i <= tt; i++){
        if (q[i].f == "add"){
            int x = q[i].s.f;
            int y = q[i].s.s;
            int pos = int(lower_bound(vec.begin(), vec.end(), make_pair(x, y)) - vec.begin()) + 1;
            update(1, 1, m, pos, y);
        }
        else if (q[i].f == "remove"){
            int x = q[i].s.f;
            int y = q[i].s.s;
            int pos = int(lower_bound(vec.begin(), vec.end(), make_pair(x, y)) - vec.begin()) + 1;
            update(1, 1, m, pos, -1);
        }
        else if (q[i].f == "find"){
            int x = q[i].s.f;
            int y = q[i].s.s;
            int pos = int(lower_bound(vec.begin(), vec.end(), make_pair(x + 1, -1)) - vec.begin()) + 1;

            int left = pos;
            int right = m;
            int ans = -1;
            while(left <= right){
                int mid = (left + right) / 2;
                if (get_max(1, 1, m, pos, mid) > y){
                    ans = mid;
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            if (ans == -1){
                cout << -1 << "\n";
            }
            else{
                cout << vec[ans - 1].f << ' ' << vec[ans - 1].s << "\n";
            }
        }
    }

    return 0;
}