No.3640 Babies don't like Bat Beat
タグ : / 解いたユーザー数 19
作問者 :
kazuppa
/ テスター :
Tamiji153
Unbakedbread
Problem Statement
There are $N$ children. Child $i$ likes songs whose speed (hereafter, BPM) is at least $L_i$ and less than $R_i$, and dislikes songs whose BPM is at least $R_i$ and less than $2L_i$. (Here, $L_i\leq R_i\leq 2L_i$ is guaranteed.)
Also, for any child, liking a song with BPM $x$ is equivalent to liking a song with BPM $2x$.
You will now choose some of the children and a positive real number $x$, and play a song with BPM $x$ only to the chosen children. This is a success if and only if all the chosen children like this song.
Find the maximum number of children with which you can succeed when the children and the BPM of the song are chosen appropriately.
Constraints
- $1\leq N\leq 2\times 10^5$
- $1\leq L_i\leq R_i\leq 10^9$
- $R_i\leq 2L_i$
- All input values are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 15 % | $N=2$ |
| Subtask 2 | 10 % | $N\leq18$ |
| Subtask 3 | 10 % | $100\leq L_i\leq R_i\leq200$ |
| Subtask 4 | 20 % | $100\leq L_i\leq R_i\leq400$ |
| Subtask 5 | 20 % | $R_i\leq10^5$ |
| Subtask 6 | 25 % | No additional constraints |
Input
$N$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_N\ R_N$
Output
Output the answer on a single line.
Sample
Sample 1
Input
5 220 300 120 200 169 231 120 240 170 250
Output
4
By choosing children $1,2,4,5$ and $x=240$, you can succeed with $4$ children.
It is impossible to succeed with more than $4$ children, so the answer is $4$.
Sample 2
Input
3 240 240 250 250 260 260
Output
0
No matter which children and $x$ you choose, you cannot succeed.
Sample 3
Input
6 591 1000 839 1472 8293 12049 6561 10201 1 2 4893 9020
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。