P1311 [NOIP 2011 Senior] Choosing Inns

Along the Lijiang River, there are $n$ distinctive inns, numbered from $1$ to $n$ in order of their locations. Each inn is decorated in one of $k$ hues (represented by integers $0 \sim k-1$), and each inn has a coffee shop with its own minimum charge. Two tourists are traveling together. They like the same hue but want to try two different inns, so they decide to stay at two inns with the same hue. At night, they plan to choose a coffee shop to have coffee. The coffee shop must be located between the two inns they stay at (including the inns themselves), and its minimum charge must not exceed $p$. They want to know the total number of ways to choose their accommodations such that they can find a coffee shop whose minimum charge is no more than $p$ yuan at night.

There are $n+1$ lines. The first line contains three integers $n, k, p$, separated by single spaces, representing the number of inns, the number of hues, and the maximum acceptable minimum charge, respectively. For the next $n$ lines, the $(i+1)$-th line contains two integers, separated by a single space, denoting the hue $a_i$ of inn $i$ and the minimum charge $b_i$ of the coffee shop of inn $i$.

Output a single integer, the total number of valid accommodation choices.

Sample Explanation.  Since the two people must stay in inns with the same hue, all possible choices include: inns $1$ and $3$, $2$ and $4$, $2$ and $5$, $4$ and $5$. However, if they choose inns $4,5$, the minimum charge of the coffee shops between inns $4$ and $5$ is $4$, while their acceptable minimum charge is $3$ yuan, so this does not satisfy the requirement. Therefore, only the first $3$ choices are valid. Constraints. - For $30\%$ of the testdata, $n \leq 100$. - For $50\%$ of the testdata, $n \leq 1\,000$. - For $100\%$ of the testdata, $2 \leq n \leq 2 \times 10^5$, $1 \leq k \leq 50$, $0 \leq p \leq 100$, $0 \leq b_i \leq 100$. Translated by ChatGPT 5