WC '17 Contest 2 S3 - Battle of the Pelennor Fields

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.75s
Memory limit: 128M

Problem type
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. N (1 \le N \le 300\,000) events will then occur over the course of the battle, one after another. The i^{th} event's type is indicated by the value E_i (1 \le E_i \le 2):

  • If E_i = 1, then an orc arrives on the battlefield at position O_i (0 \le O_i \le 10^9).
  • Otherwise, if E_i = 2, then a Gondorian archer arrives on the battlefield at position A_i (0 \le A_i \le 10^9), and having a bow range of R_i (1 \le R_i \le 10^9). Such an archer is able to shoot any orcs which are at most R_i units of distance away from A_i.

All N 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 N events, you'd like to report to Gandalf the number of orcs currently on the battlefield which are not vulnerable.


In test cases worth 4/27 of the points, N \le 1000 and R_i = 1 for each applicable i.
In test cases worth another 4/27 of the points, R_i = 1 for each applicable i.
In test cases worth another 8/27 of the points, R_i = 10^6 for each applicable i.

Input Specification

The first line of input consists of a single integer, N.
N lines follow, the i^{th} of which consists of a single integer, E_i, followed by either 1 more integer O_i (if E_i = 1) or 2 more integers A_i and R_i (if E_i = 2), for i = 1 \dots N.

Output Specification

Output N lines, the i^{th} of which should consist of a single integer, the number of non-vulnerable orcs on the battlefield after the first i events.

Sample Input

1 15
1 22
2 18 3
1 19
2 5 12
1 23
1 0

Sample Output


Sample Explanation

After the 2^{nd} event, there are still no archers on the field, meaning that both orcs are non-vulnerable. After the 3^{rd} 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 7^{th} event, the orcs at positions 22 and 23 are still non-vulnerable, while the remaining 3 orcs are vulnerable.


  • 2
    cabbagecabbagecabbage  commented on July 13, 2021, 12:05 p.m. edited

    thanks a lot. can't believe i didnt try using a custom hash in the 10 hours of optimizing...

    edit: oops didnt click reply

    • 1
      Nils_Emmenegger  commented on July 13, 2021, 1:21 p.m.

      TIL about custom hash functions. Thanks for the link!

  • 2
    Nils_Emmenegger  commented on July 13, 2021, 1:47 a.m. edited

    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.