P3997 [SHOI2013] Union of Sector Areas

 Given $n$ concentric sectors, find how much area is covered by at least $k$ sectors.

The first line contains three integers $n$, $m$, $k$. Here, $n$ is the number of concentric sectors, and $m$ means the angle interval $(-\pi, \pi]$ is evenly divided into $2m$ parts. From the second line, each of the next $n$ lines contains three integers $r, a_1, a_2$. Each line describes a sector centered at the origin with radius $r$, whose central angle ranges from radians $\pi \times \frac{a_1}{m}$ to $\pi \times \frac{a_2}{m}$ ($a_1$ is not necessarily less than $a_2$).

Output an integer $ans$, such that $\frac{\pi}{2m} \times ans$ equals the total area covered by at least $k$ sectors. It is guaranteed that the answer is within the range $2^{63} - 1$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le k \le 5000$, $1 \le r_i \le 10^5$, $-m \le a_1, a_2 \le m$. Translated by ChatGPT 5