#P5880. 遊生夢死
遊生夢死
题目描述
维护两个初始为空的点可重集 。若任一集合为空,定义 。否则定义
$$F(U,V)=\min_{\substack{(u_x,u_y)\in U\\(v_x,v_y)\in V}} \max(u_x+v_x,\ u_y+v_y).$$每次向其中一个集合插入一个点,或删除一个点的一次出现。每次操作后求 。
输入格式
第一行一个整数 ,表示操作数。接下来 行,每行四个整数 。
- 表示操作集合 , 表示操作集合 。
- 表示插入一个 。
- 表示删除一个 。保证操作前该集合至少有一个此点,重复时只删除一个。
输出格式
输出 行,第 行一个整数,表示第 次操作后的 。
样例
6
1 1 100 100
1 2 30 130
1 1 120 170
2 1 100 100
1 2 70 100
2 1 120 170
-1
230
230
300
270
-1
原题另在下发文件中提供样例 2–4。
数据范围
,,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 所有操作 | |
| 2 | 10 | |
| 3 | 20 | |
| 4 | 30 | |
| 5 | 39 | 无 |
原题来源 Gym 103627 A。