2015 Canadian Computing Olympiad

Day 1, Problem 3 - Solar Flight

A new era of aviation is upon us - the first solar-powered jumbo jets are about to be made available for public travel! However, this cutting-edge technology raises some safety concerns, as the rays of sunlight which power these planes can be blocked by other objects in the sky. As such, some statistics must first be calculated concerning the planned initial flights.

We consider a set of N flight paths, all travelling East from one city to another. A plane can be considered as a single point. The sky through which they pass can be modelled as a Cartesian plane, with x-coordinates representing distance East from an arbitrary fixed point, and y-coordinates representing altitude. We are interested only in the section of the sky with x-coordinates in the inclusive range [0, X] (1 ≤ X ≤ 10⁹), in which all flight paths are straight lines. The i-th plane flies from (0, A_i) to (X, B_i) (1 ≤ A_i, B_i ≤ 10⁹). All A values are distinct, as are all B values. The planes travel at unknown, possibly non-constant speeds along their flight paths, so at any point in time, a plane may be anywhere along its path. However, it is known that the planes will never crash with one another, so if two flight paths cross one another, both planes won't reach the intersection point at precisely the same time.

Planes also have an interference factor: each plane i has an interference factor C_i (1 ≤ C_i ≤ 10⁹), which is a measure of how much plane i would negatively impact the solar absorbing capability of any plane below them.

The solar panels on each plane are rather strange, in that they can only collect energy from directly above the plane. This means the sunlight that a given plane can absorb can be obstructed by other planes which occupy the same x-coordinate as it, and have a larger y-coordinate than it. In particular, their effectiveness is reduced based on the sum of the interference factor of all such planes.

Given this information, as well as a fixed distance constant K (1 ≤ K ≤ X), you must answer Q queries regarding the possible impact on planes' solar panels at various times. The i-th query asks for the largest possible amount by which the plane P_i's solar panels could be obstructed at a single moment in time, at any point while the plane's x-coordinate is in the inclusive range [S_i, S_i + K] (0 ≤ S_i ≤ X − K).

Input Format

The first line contains four space-separated integers: X (1 ≤ X ≤ 10⁹), the maximum x-coordinate to consider; K (1 ≤ K ≤ X), the fixed distance constant; N (1 ≤ N ≤ 2000), the number of flight paths; Q (1 ≤ Q ≤ 800,000), the number of queries.

Each of the next N lines contain three integers A_i, B_i, and C_i, for i = 1..N (1 ≤ A_i, B_i, C_i ≤ 10⁹), representing, for plane i, the starting y-coordinate, the ending y-coordinate, and the interference factor (respectively).

Each of the next Q lines contain two integers, P_i and S_i, for i = 1..Q representing the query concerning plane P_i while its x-coordinate is in the range [S_i, S_i + K].

For 40% of the marks for this problem, Q ≤ 1000.

Output Format

The output consists of Q lines, each with the integer answer to the i-th query, for i = 1..Q.

Sample Input

12 4 3 3
1 4 5
2 2 3
6 3 6
2 1
1 8
3 0

Sample Output

11
6
0

Explanation

Below is a diagram of the planes' flight paths:

The first query is for the plane 2 over x-coordinates in the inclusive range [1, 5]. While this plane is at an x-coordinate smaller than or equal to 4, it might be covered by plane 3, but definitely not by plane 1. However, when it's at an x-coordinate larger than 4, it might be covered by both other planes. Therefore, the answer to this query is the sum of the other planes' interference factors, 5 + 6 = 11.

For the second query, plane 1 could be covered by plane 3 while it has x-coordinates less than 10, and will not be covered by anything while it has x-coordinate greater than or equal to 10. Thus, it is only possibly interfered with by plane 3 with interference factor 6.

Neither plane 1 nor plane 2 can possibly be directly above plane 3 until it reaches x-coordinate 10, so the answer to the final query is 0.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 10.00s
Memory Limit: 512M
Added: Jun 05, 2015
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)