| 题目名称 | 2218. [HZOI 2015]向量vec |
|---|---|
| 输入输出 | vec.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：19， 通过率：36.84% | ||||
 stdafx.h |
100 | 2.125 s | 25.49 MiB | C++ |
 AAAAAAAAAA |
100 | 3.492 s | 14.66 MiB | C++ |
 再见 |
100 | 3.653 s | 14.02 MiB | C++ |
 qhn |
100 | 3.850 s | 6.36 MiB | C++ |
 FoolMike |
100 | 4.637 s | 11.74 MiB | C++ |
 Aglove |
100 | 4.988 s | 46.29 MiB | C++ |
 神利·代目 |
100 | 5.775 s | 8.50 MiB | C++ |
|
神利·代目 |
90 | 5.863 s | 7.16 MiB | C++ |
|
神利·代目 |
90 | 5.919 s | 7.16 MiB | C++ |
|
stdafx.h |
80 | 2.116 s | 22.94 MiB | C++ |
| 关于 向量vec 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
此生不写动态凸包，CDQ+静态凸包真的比动态凸包好些多了。懒得写归并树，于是总复杂度为O(nlog^3n)
| ||||
|
顶
顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶  Hakurou!
2016-04-10 10:38
2楼
| ||||
|
题解戳http://www.cnblogs.com/joyouth/p/5371810.html
欢迎各路神犇来踩本蒟蒻的blog Aglove
2016-04-09 17:13
1楼
| ||||
【题目描述】
你要维护一个向量集合，支持以下操作：
1. 插入一个向量(x; y)
2. 删除插入的第i 个向量
3. 查询当前集合与(x; y) 点积的最大值是多少。如果当前是空集输出0
【输入格式】
从vec.in 输入
第一行输入一个整数n，表示操作个数
接下来n 行，每行先是一个整数t 表示类型，如果t = 1，输入向量
(x; y)；如果t = 2，输入id 表示删除第id 个向量；否则输入(x; y)，查询
与向量(x; y) 点积最大值是多少。
保证一个向量只会被删除一次，不会删没有插入过的向量
输入数据保证 n<=200000, x,y<=10^6
【输出格式】
输出到vec.out
对于每条t = 3 的询问，输出一个答案
【样例输入】
5
1 3 3
1 1 4
3 3 3
2 1
3 3 3
【样例输出】
18
15