Woburn Challenge 2017-18 Round 2 - Senior Division

An enormous, decisive battle is about to take place on the Pelennor Fields before the city of Minas Tirith! A noble army of Gondorian men will engage in battle against Sauron's evil army of orcs in an attempt to save their home and all of Middle Earth. Gandalf has given you your own vital task - not to actually participate in combat, but to report to him the state of the battle as it unfolds.
The battlefield can be represented as an infinite number line, and is
initially empty.
events will then occur over
the course of the battle, one after another. The
event's type is
indicated by the value
:
- If
, then an orc arrives on the battlefield at position
.
- Otherwise, if
, then a Gondorian archer arrives on the battlefield at position
, and having a bow range of
. Such an archer is able to shoot any orcs which are at most
units of distance away from
.
All combatants' positions are distinct.
An orc is "vulnerable" if there's at least one archer on the battlefield
who is able to shoot that orc. After each of the events, you'd like
to report to Gandalf the number of orcs currently on the battlefield
which are not vulnerable.
Subtasks
In test cases worth of the points,
and
for
each applicable
.
In test cases worth another of the points,
for each
applicable
.
In test cases worth another of the points,
for
each applicable
.
Input Specification
The first line of input consists of a single integer, .
lines follow, the
of which consists of a single integer,
, followed by either
more integer
(if
) or
more integers
and
(if
), for
.
Output Specification
Output lines, the
of which should consist of a single
integer, the number of non-vulnerable orcs on the battlefield after the
first
events.
Sample Input
7
1 15
1 22
2 18 3
1 19
2 5 12
1 23
1 0
Sample Output
1
2
1
1
1
2
2
Sample Explanation
After the event, there are still no archers on the field, meaning
that both orcs are non-vulnerable. After the
event, the
newly-arrived archer is just barely able to shoot the first orc, while
the second orc is too far away and so is still non-vulnerable. After the
event, the orcs at positions
and
are still non-vulnerable,
while the remaining
orcs are vulnerable.
Comments
thanks a lot. can't believe i didnt try using a custom hash in the 10 hours of optimizing...
edit: oops didnt click reply
TIL about custom hash functions. Thanks for the link!
Coordinate compression with a gp_hash_table dies on this question for some reason, switch it out for an unordered_map or map (or another coord compression method entirely, or another solution that doesn't even use coord compression) to get your solution to pass if you're running into this.