HHPC1 P3 - Yonder Ridge

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem types

Imagine a picturesque landscape made up of various ridges stretching across an xy-plane. The x-axis of the plane extends from 0 to M, while the y-axis extends from -\infty to \infty. There are N ridges numbered from 1 to N. The i-th ridge can be represented as a line segment connecting (0, a_i) and (M, b_i), with an aesthetic value of v_i.

For an interval [l,r], the goodness of the landscape from ridge k refers the sum of the aesthetic values of other ridges that are ever strictly above the height of ridge k within [l,r].

A person is planning to explore the landscape, and has a few questions. In the i-th question, they wonder what the goodness of landscape p_i is over the interval [s_i,s_i+K]. Note that K is the same for each query.


For all subtasks:

1 \le N \le 5 \times 10^3

1 \le K \le M \le 10^9

1 \le Q \le 5 \times 10^5

-10^9 \le a_i, b_i \le 10^9

1 \le v_i \le 10^9

1 \le p_i \le N

0 \le s_i \le M - K

Subtask 1 [30%]

1 \le Q \le 5 \times 10^3

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains four space-separated integers N, M, Q, and K.

The i-th of the following N lines each contain three space-separated integers a_i, b_i, and v_i.

The i-th of the following Q lines each contain two space-separated integers p_i and s_i.

Output Specification

For each query, output an integer, representing the goodness of the landscape.

Sample Input

3 15 2 7
6 9 3
2 11 2
10 1 1
1 3
1 4

Sample Output


Sample Explanation

For the first query, only ridge 3 is ever strictly above ridge 1 in the interval [3,10], so the answer is 1.

For the second query, both ridge 2 and ridge 3 are ever strictly above ridge 1 at some point in the interval [4,11], so the answer is 1+2=3.


There are no comments at the moment.