P6641 [CCO 2020] A Game with Grundy

**All discussions in this problem take place on the Cartesian coordinate plane.** There are $N$ people. Each person has a field of view, and each person is located at $(x_i,0)$. A field of view can be modeled as an angle. **Note that the two rays that form the angle are not included in the field of view.** Now, you may stand at $(a,Y)$, where $L \le a \le R$. For each $i$ $(0 \le i \le N)$, find how many positions you can stand at such that you are inside the field of view of at most $i$ people.

The first line contains an integer $N$. The second line contains three integers $L, R, Y$. The next $N$ lines each contain three integers $x_i, v_i, h_i$. Here, $v_i$ and $h_i$ mean that the slopes of the two rays forming the angle are $\frac{v_i}{h_i}$ and $\frac{-v_i}{h_i}$, and one endpoint is at $(x_i,0)$.

There are $N+1$ lines, each containing one integer. The value on line $i$ indicates the number of positions where you can stand such that you are inside the field of view of at most $i-1$ people.

#### Sample Explanation  #### Subtasks **This problem uses bundled testdata.** - Subtask 1 ($60$ points): It is guaranteed that $-10^6 \le L \le R \le 10^6$. - Subtask 2 ($40$ points): No additional constraints. For $100\%$ of the testdata, it is guaranteed that $1 \le N \le 10^5$, $-10^9 \le L \le R \le 10^9$, $1 \le Y \le 10^6$, $1 \le x_i \le R$, and $1 \le v_i, h_i \le 100$. #### Notes This problem is translated from [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/index.html) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day1.pdf) T1 A Game with Grundy. Translated by ChatGPT 5