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 10⁶ desks, all arranged in a single row and numbered 1..10⁶ from left to right. The i-th student to arrive has a social standing of S_i (1 ≤ S_i ≤ 10⁶), and will sit at desk D_i (1 ≤ D_i ≤ 10⁶). 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 R_i (1 ≤ R_i ≤ 10⁶) desks away from the i-th student will also start doing so (in other words, each student j such that S_j < S_i and D_i − R_i ≤ D_j ≤ D_i + R_i). 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.

Subtasks

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.

Input Format

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, S_i, D_i, and R_i, for i = 1..N.

Output Format

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.

Sample Input

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

Sample Output

1
1
2
3
2
3
3
1

Sample Explanation

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.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 8.00s
Memory Limit: 256M
Added: Nov 17, 2018
Author: SourSpinach

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

Comments (Search)

I submitted my code for all four problems and got 0 points due to compile error that I couldn't fix because judge was down. Apparently the judge uses C89 or something. I fixed the compile error after the contest and I got 13 20 8 40. Surely I deserve some recognition for my innovative addition to the list of worst ways to fail a contest.

An interesting predicament indeed... You would've gotten 6th place by that account. However, it looks like you haven't registered for the contest. Are you eligible to compete officially?
If so, email [email protected] and the contest organizers might be able to award you a prize regardless.