真的球球了!!卡了两个小时了
一直卡不过 #13,写的两个 log 的树状数组套 set。
悬关两个。
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rep(i, a, b) for (register int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (register int i = (a); i < (b); i ++ )
using namespace std;
#define gc getchar
#define pc putchar
inline int read() {
int s = 0, f = 0; char ch = gc();
while (ch < '0' or ch > '9') { if (ch == '-') f = 1; ch = gc(); }
while (ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + (ch ^ 48); ch = gc(); }
return f ? -s : s;
}
inline void print(int x){
if(x <= 9) putchar('0' + x);
else print(x / 10), putchar('0' + x % 10);
}
typedef pair<int, int> PII;
const int N = 200010;
const int INF = 0x3f3f3f3f;
set<PII> s[N];
int n, lim, p[N];
struct Q {
int op, x, y;
}q[N];
inline int find(int x) {
return lower_bound(p + 1, p + lim, x) - p;
}
inline void add(int k, int x, int y) {
for (int i = k; i; i -= (i & -i))
s[i].insert(mp(x, y));
}
inline void del(int k, int x, int y) {
for (int i = k; i; i -= (i & -i))
s[i].erase(mp(x, y));
}
inline PII ask(int k, int x, int y) {
PII ans = mp(INF, INF);
for (int i = k; i <= lim; i += (i & -i))
ans = min(ans, *s[i].lower_bound(mp(x, y)));
return ans;
}
int main() {
n = read();
rep(i, 1, n) {
char ch[7]; int x, y;
scanf("%s", ch); x = read(), y = read();
if (*ch == 'a') q[i] = {0, x, y};
if (*ch == 'r') q[i] = {1, x, y};
if (*ch == 'f') q[i] = {2, ++ x, ++ y};
p[ ++ lim] = y;
} sort(p + 1, p + lim + 1);
lim = unique(p + 1, p + lim + 1) - p + 1;
rep(i, 1, lim) s[i].insert(mp(INF, INF));
rep(i, 1, n) {
if (q[i].op == 0) add(find(q[i].y), q[i].x, q[i].y);
if (q[i].op == 1) del(find(q[i].y), q[i].x, q[i].y);
if (q[i].op == 2) {
register PII ans = ask(find(q[i].y), q[i].x, q[i].y);
if (ans.first == INF) pc('-'), pc('1'), pc('\n');
else print(ans.first), pc(' '), print(ans.second), pc('\n');
}
} return 0;
}