1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f; inline int Max(int a,int b){return a>b?a:b;}
const int maxn = 2e5 + 20; int maxy[maxn<<2],mark[maxn],x[maxn],y[maxn]; set<int> s[maxn]; int n,m; char op[20]; vector<int> v; void build(int l,int r,int rt){ if(l==r){ maxy[rt] = -1; return; }else{ int mid = (l+r)>>1; build(lson); build(rson); } } void pushup(int rt){ maxy[rt] = Max(maxy[rt<<1],maxy[rt<<1|1]); } void update(int pos,int val,int l,int r,int rt){ if(l==r){ maxy[rt] = val; return; } int mid = (l+r)>>1; if(pos <= mid) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } int query(int L,int R,int val,int l,int r,int rt){ if(maxy[rt] <= val) return -1; if(l==r) return l; int mid = (l+r)>>1; int ans = -1; if(L <= mid && maxy[rt<<1] > val){ ans = query(L,R,val,lson); if(ans != -1) return ans; } if(R > mid && maxy[rt<<1|1] > val) ans = query(L,R,val,rson); return ans; } int main(){ #ifdef LOCAL freopen("points.in","r",stdin); #endif scanf("%d",&n); rep(i,0,n){ scanf("%s%d%d",op,&x[i],&y[i]); if(op[0] == 'a') mark[i] = 1; else if(op[0] == 'r') mark[i] = 2; else mark[i] = 3; if(op[0] == 'a') v.push_back(x[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); m = v.size(); rep(i,0,n){ if(mark[i] == 1 || mark[i] == 2){ int pos = lower_bound(v.begin(),v.end(),x[i]) - v.begin()+1; if(mark[i] == 1) s[pos].insert(y[i]); else s[pos].erase(y[i]); int val; if(s[pos].empty()) val = -INF; else val = *(--s[pos].end()); update(pos,val,1,m,1); }else{ int pos = upper_bound(v.begin(),v.end(),x[i]) - v.begin()+1; int z = query(pos,m,y[i],1,m,1); if(z == -1 || pos == m+1){ puts("-1"); continue; } int ans = *(s[z].upper_bound(y[i])); printf("%d %d\n",v[z-1],ans); } } return 0; }
|