Woburn Challenge 2018-19 Round 1 - Senior Division
Problem 4: Bad Influence
N (1 ≤ N ≤ 300,000) students are filing into H.S. High School's popular French class, one after another. The classroom has a whopping 106 desks, all arranged in a single row and numbered 1..106 from left to right. The i-th student to arrive has a social standing of Si (1 ≤ Si ≤ 106), and will sit at desk Di (1 ≤ Di ≤ 106). All N students have distinct social standings and will sit at distinct desks.
Even though the students love learning French, they sometimes still get distracted by their phones and stop paying attention in class. Furthermore, this issue is exasperated by the effects of peer pressure! If the i-th student were to start using their phone, all students with smaller social standings who are sitting no further than Ri (1 ≤ Ri ≤ 106) desks away from the i-th student will also start doing so (in other words, each student j such that Sj < Si and Di − Ri ≤ Dj ≤ Di + Ri). As a result of those students using their phones, even more students may in turn start using their phones, and so on.
When one or more students are present in the classroom, the "volatility" of that set of students is defined as the minimum number of students who would need to initially start using their phones by themselves, such that all of the students currently present would end up using their phones.
As the students file in, the French teacher wants to keep track of the volatility of her class, to give her an idea of what she'll be in for. So, after each student i sits down, the teacher is interested in the volatility of the students present so far (students 1..i). Please help her compute this list of N volatilities.
In test cases worth 8/40 of the points, N ≤ 10.
In test cases worth another 6/40 of the points, N ≤ 300.
In test cases worth another 8/40 of the points, N ≤ 3000.
The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of three space-separated integers, Si, Di, and Ri, for i = 1..N.
Output N lines, the i-th of which should consist of a single integer, the volatility after the first i students have arrived, for i = 1..N.
8 14 5 1 8 6 3 12 1 3 19 8 2 21 7 3 10 11 1 3 10 6 13 9 10
1 1 2 3 2 3 3 1
After the first student arrives, it would be necessary for just them to start using their phone, resulting in a volatility of 1.
After the second student arrives, it would still only be necessary for student 1 to start using their phone, as that would also cause student 2 to also use their phone. Therefore, the volatility of these two students is still 1.
After the third student arrives, it would be necessary for at least two of the three students to start using their phones (students 1 and 3). Therefore, the volatility of these three students is 2.
Once all students are present, they would all end up using their phones if only student 5 initially decided to use their phone. Therefore, the volatility of all 8 students is 1.
Point Value: 15 (partial)
Time Limit: 8.00s
Memory Limit: 256M
Added: Nov 17, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3