P7564 [JOISC 2021] Bodyguard (Day3)

Because the data package is too large, if the wrong testdata cannot be downloaded on Luogu, please get the full data [here](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/bodyguard-data.zip).

On a number line, there are $N$ people, and they are all customers of the Bookworm Bodyguard Company. Customer $i$ will move from position $A_i$ to position $B_i$ at time $T_i$. Their speed is one unit of length per unit of time. If a bodyguard and a customer are at the same position at the same time, we say that the bodyguard is protecting that customer. Suppose the bodyguard starts protecting customer $i$ at time $a$ and stops protecting at time $b$. Then the interval $[a,b]$ is called the protection time of this customer, time $a$ is called the start time of protection, and time $b$ is called the stop time of protection. **Here, $a$ and $b$ do not have to be integers**. In particular, if a bodyguard is at the same position at the same time with two customers, the bodyguard can protect only one customer. A bodyguard can move freely on the number line with speed at most one unit of length per unit of time and at least staying still. When a bodyguard stops protecting one customer, they can go to another position to protect another customer. If the path length that the bodyguard walks together with customer $i$ while protecting them is $L$, then customer $i$ will pay the bodyguard $L \times C_i$ Zimbabwe dollars, at a rate of $C_i$ Zimbabwe dollars per unit length. As the owner of the Bookworm Bodyguard Company, Bookworm holds $Q$ planned protection proposals. In proposal $j$, a bodyguard starts working at time $P_j$ from position $X_j$. For each proposal, find the maximum total wage (in Zimbabwe dollars) that the bodyguard can earn.

The first line contains two integers $N,Q$, representing the number of customers and the number of planned protection proposals. The next $N$ lines each contain four integers $T_i,A_i,B_i,C_i$, describing one customer. The next $Q$ lines each contain two integers $P_j,X_j$, describing one planned protection proposal.

Output $Q$ lines. Each line contains one integer, representing the maximum total wage (in Zimbabwe dollars) that the bodyguard can earn for the corresponding proposal.

#### Explanation for Sample 1 - In proposal $1$, the bodyguard can earn $4+4=8$ Zimbabwe dollars in the following way. - Start moving from position $2$ at time $1$. - Protect customer $1$ from time $1$ to time $2$. The path length traveled together is $1$, so the wage is $4 \times 1=4$ Zimbabwe dollars. - Stay at position $1$ from time $2$ to time $3$. - Protect customer $2$ from time $3$ to time $5$. The path length traveled together is $2$, so the wage is $2 \times 2=4$ Zimbabwe dollars. - In proposal $2$, the bodyguard can earn $2$ Zimbabwe dollars in the following way. - Start moving from position $3$ at time $3$. - Move from position $3$ to position $2$ from time $3$ to time $4$. - Protect customer $2$ from time $4$ to time $5$. The path length traveled together is $1$, so the wage is $2 \times 1=2$ Zimbabwe dollars. #### Explanation for Sample 2 - In proposal $1$, the bodyguard can earn $4+1+8+2=15$ Zimbabwe dollars in the following way. - Start moving from position $2$ at time $2$. - Move from position $2$ to position $2.5$ from time $2$ to time $2.5$. - Protect customer $2$ from time $2.5$ to time $3.5$. The path length traveled together is $1$, so the wage is $4 \times 1=4$ Zimbabwe dollars. - Protect customer $1$ from time $3.5$ to time $4$. The path length traveled together is $0.5$, so the wage is $2 \times 0.5=1$ Zimbabwe dollars. - Protect customer $3$ from time $4$ to time $6$. The path length traveled together is $2$, so the wage is $4 \times 2=8$ Zimbabwe dollars. - Protect customer $1$ from time $6$ to time $7$. The path length traveled together is $1$, so the wage is $2 \times 1=2$ Zimbabwe dollars. - In proposal $2$, no matter how the bodyguard moves, they cannot earn any wage, and can only get $0$ Zimbabwe dollars. #### Constraints and Notes **This problem uses bundled subtasks.** - Subtask 1 (6 pts): $T_i,A_i,B_i,P_j,X_j \le 3000$. - Subtask 2 (7 pts): $Q=1$. - Subtask 3 (15 pts): $Q \le 3000$. - Subtask 4 (20 pts): $Q \le 4 \times 10^4$. - Subtask 5 (52 pts): No special restrictions. For all testdata, $1 \le N \le 2800$, $1 \le Q \le 3 \times 10^6$, $1 \le T_i,A_i,B_i,C_i \le 10^9$, $A_i \ne B_i$, $C_i$ is even, and $1 \le P_j,X_j \le 10^9$. #### Note Translated from [The 20th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html), [Day3 B ボディーガード (Bodyguard) English version](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/bodyguard-en.pdf). Translated by ChatGPT 5