Woburn Challenge 2015-16 Round 3 - Senior Division

Problem 4: Lex Luthor's Landmines

Lex Luthor's international masquerade as a humanitarian has attracted the attention of Princess Diana of Themyscira, also known as Wonder Woman. Thanks to her unexpected addition to team Batman and Superman, all the prisoners from Cadmus have fortunately been rescued. But it's too late. Luthor has already unleashed his dangerous bio-weapon of unimaginable power – Doomsday. To destroy the reputation of Superman, Doomsday has been wreaking havoc and causing wanton destruction upon Metropolis. Doomsday was originally a deadly monster born from the depths of ancient Krypton. Having worked so hard to reanimate the abominable legend from his very own laboratories on Earth, Luthor might as well make this moment count.

The mastermind knows for a fact that while Doomsday is trampling the city, the heroes will be intently focused on minimizing civilian casualties. To further tie up their hands during their clash with Doomsday, he has decided to throw in the age-old weapon of landmines. The current street of the fight can be represented as a number line of integer positions numbered from 0 to 10⁹, inclusive. Luthor has planted N (1 ≤ N ≤ 10⁶) landmines at (not necessarily distinct) positions on the street, where each landmine is numbered uniquely from 1 to N. The i-th landmine is located at position X_i (0 ≤ X_i ≤ 10⁹) on the street. But there is a catch – these landmines have been specially engineered to explode in an asymmetrical fashion. When the i-th landmine goes off, its explosion reaches L_i (1 ≤ L_i ≤ 10⁹) units to the left (in the negative direction), and R_i (1 ≤ R_i ≤ 10⁹) units to the right (in the positive direction). As such, its explosion reaches all positions in the inclusive range [X_i − L_i, X_i + R_i] on the street.

Lex Luthor will control Doomsday to set off exactly one landmine of his choice – however, this may start a chain reaction! If any other landmines are within the initial landmine's explosion range, they'll also go off. Their explosions may in turn set off even more landmines, and so forth. As if fighting the deadly beast isn't enough on their plates, Batman, Superman, and Wonder Woman will need to evacuate the citizens of the street to safety from the landmines. To do so, they will have to evaluate how dangerous certain positions on the street are. They know that M (1 ≤ M ≤ 300,000) civilians numbered from 1 to M are currently located at possibly non-distinct points on the street, where the i-th civilian is located at position C_i (0 ≤ C_i ≤ 10⁹). For each civilian i, they'd like to know the number of different initial landmines that Doomsday could set off which would cause that civilian to be engulfed in at least one of the resulting explosions. Please write a program to help the trio answer these questions. Superman's reputation is dwindling with every moment of Metropolis's destruction and countless civilian lives are at stake, so you'd better code fast!

For cases worth 30% of the points, N ≤ 500 and M ≤ 500.

Input Format

The first line of input will contain two space-separated integers N and M.
The next N lines will each contain three space-separated integers X_i, L_i, and R_i, for i = 1..N.
The next M lines will each contain a single integer C_i, for i = 1..M.

Output Format

Output M lines, each containing a single integer – the number of initial landmines which would cause the civilian at position C_i to be engulfed by an explosion, for i = 1..M.

Sample Input

4 4
10 5 12
4 5 6
15 1 1
20 10 80
101
100
0
14

Sample Output

0
3
1
4

Explanation

Position 101 is too far to be within any possible explosion.
Position 100 will be engulfed by the 4th landmine's explosion if either the 1st, 2nd, or 4th landmine is initially set off. If the 2nd one is set off, for example, its explosion will set off the 1st landmine, which will set off the 4th one, which will just barely reach the point.
Position 0 will only be engulfed if the 2nd landmine is initially set off.
No matter which landmine is initially set off, position 14 will always be engulfed.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 4.00s
Memory Limit: 512M
Added: Feb 13, 2016
Authors: SourSpinach, Alex

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

Comments (Search)