# CodeForces 19D Points (线段树+set)

D. Points

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Pete and Bob invented a new interesting game. Bob takes a sheet of paper and locates a Cartesian coordinate system on it as follows: point (0, 0) is located in the bottom-left corner, Ox axis is directed right, Oy axis is directed up. Pete gives Bob requests of three types:

• add x y — on the sheet of paper Bob marks a point with coordinates (x, y). For each request of this type it's guaranteed that point (x, y) is not yet marked on Bob's sheet at the time of the request.
• remove x y — on the sheet of paper Bob erases the previously marked point with coordinates (x, y). For each request of this type it's guaranteed that point (x, y) is already marked on Bob's sheet at the time of the request.
• find x y — on the sheet of paper Bob finds all the marked points, lying strictly above and strictly to the right of point (x, y). Among these points Bob chooses the leftmost one, if it is not unique, he chooses the bottommost one, and gives its coordinates to Pete.

Bob managed to answer the requests, when they were 10, 100 or 1000, but when their amount grew up to 2·105, Bob failed to cope. Now he needs a program that will answer all Pete's requests. Help Bob, please!

Input

The first input line contains number n (1 ≤ n ≤ 2·105) — amount of requests. Then there follow n lines — descriptions of the requests. add x y describes the request to add a point, remove x y — the request to erase a point, find x y — the request to find the bottom-left point. All the coordinates in the input file are non-negative and don't exceed 109.

Output

For each request of type find x y output in a separate line the answer to it — coordinates of the bottommost among the leftmost marked points, lying strictly above and to the right of point (x, y). If there are no points strictly above and to the right of point (x, y), output -1.

Examples

input

```7
find 0 0
remove 1 1
find 0 0
find 0 0```

output

```1 1
3 4
1 1```

input

```13
find 6 6
remove 7 7
find 6 6
find 4 4```

output

```7 7
-1
5 5

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <set>

using namespace std;
typedef long long int LL;
const int maxn=2*1e5;
const int INF=0x7FFFFFFF;
int p;
int rt[maxn+5];
int ls[maxn*35+5];
int rs[maxn*35+5];
int sum[maxn*35+5];
set<int> a[maxn*35+5];
int n,m;
set<int>::iterator it;
int newnode()
{
ls[p]=rs[p]=0;
sum[p]=-1;
return p++;
}
int nn;
void pushup(int node)
{
if(!ls[node]&&rs[node])
sum[node]=sum[rs[node]];
else if(!rs[node]&&ls[node])
sum[node]=sum[ls[node]];
else if(ls[node]&&rs[node])
sum[node]=max(sum[ls[node]],sum[rs[node]]);
else
sum[node]=-1;
}
void update(int &node,int l,int r,int tag,int tag2,int flag)
{
if(!node) node=newnode();
if(l==r)
{
if(flag)
{

a[node].insert(tag2);
if(a[node].empty()) sum[node]=-1;
else
{
it=a[node].end();
it--;
sum[node]=*(it);
}
}
else
{
a[node].erase(tag2);
if(a[node].empty()) sum[node]=-1;
else
{
it=a[node].end();
it--;
sum[node]=*(it);
}
}

return;
}
int mid=(l+r)>>1;
if(tag<=mid) update(ls[node],l,mid,tag,tag2,flag);
else update(rs[node],mid+1,r,tag,tag2,flag);
pushup(node);
}
int query(int node,int l,int r,int tag,int y)
{
if(!node) return -1;
if(y>=sum[node]) return -1;

if(l==r)
{

nn=*a[node].upper_bound(y);
return l;
}
int ret;
int mid=(l+r)>>1;
if(tag>=mid) ret=query(rs[node],mid+1,r,tag,y);
else
{
ret=query(ls[node],l,mid,tag,y);
if(ret==-1)
ret=query(rs[node],mid+1,r,tag,y);
}
return ret;
}
int main()
{
scanf("%d",&n);
char c[10];
p=1;
int root=0;
int x,y;
int r=1e9;
for(int i=1;i<=n;i++)
{
scanf("%s",c);
scanf("%d%d",&x,&y);
if(c[0]=='a')
{
update(root,0,r,x,y,1);
}
else if(c[0]=='r')
{
update(root,0,r,x,y,0);
}
else if(c[0]=='f')
{
nn=INF;
int xx=query(root,0,r,x,y);
if(xx==-1||nn==INF)
{
printf("-1\n");
continue;
}
printf("%d %d\n",xx,nn);
}
}
return 0;
}```

0 条评论

## 相关文章

1513

3515

### 1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2874

3475

### 习题4：变量和命名

"_"下划线这个符号在变量里通常被用作假象的空格，用来隔开单词，切记千万不要用"-"这个符号来连接单词

592

962

### 2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2855

### 对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会...

2822

### 1012. 变换密码

1012. 变换密码 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 一密码变换规则如下：一...

3304

932