Canadian Computing Olympiad: 2015 Day 1, Problem 3
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
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
(
), in which all flight paths are straight lines.
The
plane flies from
to
(
). All
values are distinct, as are all
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
has an
interference factor
(
), which is a measure
of how much plane
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
(
), you must answer queries regarding the possible
impact on planes' solar panels at various times. The
query asks
for the largest possible amount by which the plane'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
.
Input Specification
The first line contains four space-separated integers:
(
),
the maximum x-coordinate to consider;
(
), the fixed distance
constant;
(
), the number of flight paths;
(
), the number of queries.
Each of the next
lines contain three integers,
,
, and
,
for
(
), representing, for plane
,
the starting y-coordinate, the ending y-coordinate, and the interference factor,
respectively.
Each of the next
lines contain two integers,
and
, for
representing the query concerning plane
while its x-coordinate is in the
range
.
For 40% of the marks for this problem,
.
Output Specification
The output consists of
lines, each with the integer answer to the
query, for
.
Sample Input
Copy
12 4 3 3
1 4 5
2 2 3
6 3 6
2 1
1 8
3 0
Output for Sample Input
Copy
11
6
0
Explanation of Output for Sample Input
Below is a diagram of the planes' flight paths:
The first query is for plane
over x-coordinates in the inclusive range
. While this plane is at an x-coordinate smaller than or equal to
,
it might be covered by plane
, but definitely not by plane
. However,
when it's at an x-coordinate larger than
, it might be covered by both other planes.
Therefore, the answer to this query is the sum of the other planes' interference factors,
.
For the second query, plane
could be covered by plane
while it has
x-coordinate less than
, and will not be covered by anything while it
has x-coordinate greater than or equal to
. Thus, it is only possibly
interfered with by plane
with interference factor
.
Neither plane
nor plane
can possibly be directly above plane
until
it reaches x-coordinate
, so the answer to the final query is
.
Comments
Could someone help me out here?
https://codeforces.com/blog/entry/53976