Problem F
CCC Camp
Languages
en
sv
It’s time for a new camp in Härryda with Chalmers Coding Club! As per tradition, everyone has been in the sauna until 3 AM and has now gone to bed. The entire camp is sleeping together in a large, elongated room (Storstugan), but unfortunately, there is also a window along the long side facing directly towards the morning sun, which will soon rise. There are $N$ participants, where the $i$:th participant sleeps $d_i$ meters from the door (on the short side) of the room. Since the participants sleep in bunkbeds, it is possible that multiple participants sleep equally far from the door.
Rasmus has woken up early and notices that there are a number of curtains covering parts of the window at $M$ different intervals. Each curtain blocks the sunlight for everyone sleeping between $L$ and $R$ (inclusive) meters from the door, allowing them to keep sleeping. Note that multiple curtains may cover the same part of the window. Unfortunately, those who are not covered by a section of the curtain will be hit by the strong morning sun and wake up immediately.
To help all the poor participants who will wake up early, Rasmus plans to make coffee. He assumes that each participant will need one cup of coffee to wake up properly, but he also knows that Joshua and Gustav stayed up even later to prepare for the next day’s lectures, so they will need two cups of coffee.
How many cups of coffee does Rasmus need to make?
Input
The first line contains two integers $N$ and $M$ ($1 \leq N \leq 2 \cdot 10^5$, $0 \leq M \leq 2 \cdot 10^5$), the number of participants and the number of curtain segments.
This is followed by $N$ lines, where the $i$:th line contains the name of the $i$:th participant followed by $d_i$ ($0 \leq d_i \leq 10^9$), the distance from the door at which they sleep. Each name consists of 3 to 10 letters. It starts with an uppercase letter (A-Z), followed by lowercase letters (a-z). It is guaranteed that each participant’s name is unique.
The next $M$ lines each contain two integers, $L$ and $R$ ($0 \le L_j \le R_j \le 10^9$), indicating that a curtain covers the interval $[L, R]$. Note that some curtains may overlap.
Output
Print an integer: the number of cups of coffee Rasmus needs to prepare to satisfy the newly awakened participants.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$10$ |
$N, M \le 100$, $d_i, L_j, R_j \le 1000$ |
|
$2$ |
$20$ |
$M \le 100$, $d_i, L_j, R_j \le 10^5$ |
|
$3$ |
$20$ |
$d_i, L_j, R_j \le 10^5$ |
|
$4$ |
$50$ |
No additional constraints. |
Explanation of Sample 1
Unfortunately, Joshua, Jens, and Gustav will wake up. Joshua and Gustav need two cups of coffee each, while Jens only needs one. Therefore, Rasmus needs to brew a total of 5 cups of coffee.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 Jens 0 Loke 1 Joel 3 Joshua 6 Gustav 7 Sebastian 8 1 5 8 8 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 Julia 3 Joshua 10 Erik 6 Gustav 2 Hugo 13 4 6 1 5 |
3 |
