A875. Apple Catching--Gold
编程题
提高+/省选-
知识点
题目描述
It's raining apples! At certain points in time, some number of apples will hit
the number line. At certain points in time, some of Farmer John's cows will
arrive on the number line and start catching apples.
If an apple hits the number line without a cow to catch it, it is lost
forever. If a cow and an apple arrive at the same time, the cow catches it.
Each cow can travel one unit per second. Once a cow catches a single apple,
she exits the number line.
If FJ's cows collaborate optimally, how many apples can they catch in total?
the number line. At certain points in time, some of Farmer John's cows will
arrive on the number line and start catching apples.
If an apple hits the number line without a cow to catch it, it is lost
forever. If a cow and an apple arrive at the same time, the cow catches it.
Each cow can travel one unit per second. Once a cow catches a single apple,
she exits the number line.
If FJ's cows collaborate optimally, how many apples can they catch in total?
输入格式
The first line contains $N$ ($1\le N\le 2\cdot 10^5$), the number of times
apples hit the number line or FJ's cows appear.
The next $N$ lines each contain four integers $q_i$, $t_i$, $x_i$, and $n_i$
($q_i\in \\{1,2\\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$).
* If $q_i=1$, this means that $n_i$ of FJ's cows arrive on the number line at time $t_i$ at location $x_i$.
* If $q_i=2$, this means that $n_i$ apples will hit the number line at time $t_i$ at location $x_i$.
It is guaranteed that all of the ordered pairs $(t_i,x_i)$ are distinct.
apples hit the number line or FJ's cows appear.
The next $N$ lines each contain four integers $q_i$, $t_i$, $x_i$, and $n_i$
($q_i\in \\{1,2\\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$).
* If $q_i=1$, this means that $n_i$ of FJ's cows arrive on the number line at time $t_i$ at location $x_i$.
* If $q_i=2$, this means that $n_i$ apples will hit the number line at time $t_i$ at location $x_i$.
It is guaranteed that all of the ordered pairs $(t_i,x_i)$ are distinct.
输出格式
The maximum number of apples FJ's cows may collectively catch.
输入输出样例
输入 #1
5 2 5 10 100 2 6 0 3 2 8 10 7 1 2 4 5 1 4 7 6
输出 #1
10
说明/提示
In this example, none of the $100$ apples that land at time $t=5$ may be
caught. Here is a way for $10$ apples to be caught:
* All six of FJ's cows that arrive at time $t=4$ catch one of the apples that land at time $t=8$.
* One of FJ's cows that arrive at time $t=2$ catches one of the apples that land at time $t=8$.
* Three of the remaining cows that arrive at time $t=2$ catch one of the apples that land at time $t=6$.
caught. Here is a way for $10$ apples to be caught:
* All six of FJ's cows that arrive at time $t=4$ catch one of the apples that land at time $t=8$.
* One of FJ's cows that arrive at time $t=2$ catches one of the apples that land at time $t=8$.
* Three of the remaining cows that arrive at time $t=2$ catch one of the apples that land at time $t=6$.