P6964: 接苹果
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John
的一些奶牛将到达数轴并开始接苹果。
如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。
如果 FJ
的奶牛以最优方式合作，她们总共能接住多少个苹果？
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
（1≤N≤2×10
^5
），为苹果落到数轴上的次数或 FJ
的奶牛出现的次数。
以下 N
行每行包含四个整数 qi，ti
，xi
和 ni（qi∈{1,2},0≤ti≤10
^9,0≤xi≤10
^9,1≤ni≤10
^3
）。
1.如果 qi=1
，意味着 FJ
的 ni 头奶牛在 ti 时刻来到数轴上的 xi 位置。
2.如果 qi=2
，意味着 ni
个苹果在 ti 时刻落到了数轴上的 xi 位置。
输入保证所有有序对 (ti,xi)
各不相同。
【
输出格式】
（输出至终端 /
标准输出）：
输出 FJ
的奶牛总计能接住的苹果的最大数量。
【
输入样例】
：
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6
【
输出样例】
：
10
【样例说明】
在这个例子中，在 t=5
时刻落地的 100 个苹果均不能被接住。以下是一种接住 10 个苹果的方式：
FJ
的所有六头 t=4 时刻到达的奶牛各接一个 t=8 时刻落地的苹果。
FJ
的一头 t=2 时刻到达的奶牛接一个 t=8 时刻落地的苹果。
余下三头 t=2
时刻到达的奶牛各接一个 t=6 时刻落地的苹果。
【
输入样例】
：
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6
【
输出样例】
：
9
【样例说明】
在 t=5
时刻落地的苹果均不能被接住。除此之外，在 t=2 时刻到达的奶牛均不能接住 t=8 时刻落地的苹果。以下是一种接住 9 个苹果的方式：
FJ
的所有六头 t=4 时刻到达的奶牛各接一个 t=8 时刻落地的苹果。
余下三头 t=2
时刻到达的奶牛各接一个 t=6 时刻落地的苹果。