曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5741: findpair

Memory Limit：128 MB Time Limit：2.000 S
Judge Style：Text Compare Creator：
Submit：45 Solved：35
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

有一个平面，维护两种操作：
1.加入一个点 (x,y)
2.查询一个点 (x,y) 到第一个比它大的点（比它大的中最小的一个的点）的曼哈顿距离 dis=|x1-x2|+|y1-y2|
若 a(x1,y1) b(x2,y2) 有 x1>x2 或 (x1==x2且y1>y2) 则 a>b

Input

第一行 n (n≤100000) 表示操作个数。
第 2..n+1 行，每行 3 个整数 opt,x,y。
若 opt==1 则加入一个点 (x,y)。
若 opt==2 则对 (x,y) 进行一次查询。

Output

对于 opt==2 输出距离，一行一个，若不存在,输出 -1 。

Sample Input Copy 

8
1 3 4
2 3 3
2 4 3
2 3 4
1 5 5
2 1 1
2 4 5
2 3 2
1 6 6

Sample Output Copy 

1
-1
-1
5
1
2

HINT

set, pair

Source/Category