Самокаттарды жалға беру
Қалада самокаттарды жалға беру станциясы жұмыс істейді. Күн ішінде станцияға самокаттардың партиялары келіп түседі. Әр самокаттың заряд деңгейі бар — оны шектеулі уақыт бойы пайдалануға болады, содан кейін ол зарядтауға кетеді және қолжетімсіз болады.
Сонымен қатар, күн ішінде туристік топтардан өтінімдер келеді. Әр топ сапарға шығуды қалайды, және оларға дәл \(s\) самокат қажет. Өтінім тек оның келіп түскен сәтінде орындалуы мүмкін, егер сол сәтте станцияда кемінде \(s\) самокат әлі пайдаланылмаған және заряды бар болса. Бұл жағдайда \(s\) самокат беріледі, және топ самокатпен кетеді. Егер самокаттар жеткіліксіз болса — топ самокатсыз кетеді. Өтінімді орындау кезінде станцияда сол сәтте бар кез келген \(s\) сәйкес самокаттарды таңдауға болады. Ең бастысы, олардың әлі заряды бар және бұрын пайдаланылмаған болуы керек.
\(t_i\) уақытында \(d_i\) зарядпен келген самокаттар \(t_i + d_i\) уақытқа дейін (қоспағанда) қолжетімді. Әр самокатты бір реттен артық пайдалануға болмайды.
Орындауға болатын өтінімдердің максималды санын анықтаңыз.
Енгізу
Бірінші жолда екі бүтін сан \(k\) және \(s\) — самокаттардың жеткізілім саны және бір топқа қажетті самокаттар саны \((1 \le k \le 2 \cdot 10^5,\ 1 \le s \le 10^9)\).
Келесі \(k\) жолда үш бүтін сан \(t_i\), \(a_i\), \(d_i\) — \(i\)-ші жеткізілімнің келу уақыты, самокаттар саны және заряд деңгейі \((1 \le t_i \le 10^9,\ 1 \le a_i, d_i \le 10^9)\).
Келесі жолда бір бүтін сан \(n\) — топтар саны \((1 \le n \le 2 \cdot 10^5)\).
Келесі жолда \(n\) бүтін сан \(q_j\) — \(j\)-ші өтінімнің келу уақыты \((1 \le q_j \le 10^9)\).
\(t_1 \le t_2 \le \cdots \le t_k\) және \(q_1 \le q_2 \le \cdots \le q_n\) екендігіне кепілдік беріледі.
Шығару
Бір бүтін санды шығарыңыз — самокаттарды алуға болатын топтардың ең көп саны.
Бағалау жүйесі
| Ішесеп | Қосымша шектеулер | Ұпайлар | Қажетті ішесептер |
|---|---|---|---|
| \(0\) | Мысалдар | \(0\) | — |
| \(1\) | Барлық \(t_i=1\), барлық \(d_i=10^9\), \(n, k \le 1000\) | \(13\) | — |
| \(2\) | \(t_i + d_i \le t_{i+1}\)(әр сәтте бір жеткізілім ғана белсенді) | \(18\) | — |
| \(3\) | Барлық \(d_i = 10^9\) (яғни самокаттар заряды бітпейді) | \(19\) | \(1\) |
| \(4\) | \(n, k \le 1000\) | \(21\) | \(1\) |
| \(5\) | Қосымша шектеулерсіз | \(29\) | \(1,2,3,4\) |
Мысалдар
Енгізу 1
4 3
1 4 5
2 4 2
4 1 2
5 1 3
5
1 2 3 4 5Жауап 1
3Ескертпелер
Әр өтінім \(s = 3\) самокатты талап етеді.
\(1\) сәтінде бірінші жеткізілім келеді: \(4\) самокат, \([1, 6)\) аралығында әрекет етеді.
\(1\) сәтіндегі өтінім: \(4\) самокат қолжетімді \(\rightarrow\) орындалады, \(3\) пайдаланылады \(\rightarrow\) бірінші жеткізілімнен \(1\) қалады.
\(2\) сәтінде екінші жеткізілім келеді: \(4\) самокат, \([2, 4)\) аралығында әрекет етеді.
\(2\) сәтіндегі өтінім: \(1\) (біріншіден) + \(4\) (екіншіден) қолжетімді \(\rightarrow\) екіншіден \(3\) таңдаймыз \(\rightarrow\) өтінім орындалады \(\rightarrow\) бірінші жеткізілімнен \(1\) және екінші жеткізілімнен \(1\) қалады.
\(3\) сәтіндегі өтінім: 1 және 2 жеткізілімдері әрекет етеді \(\rightarrow\) \(1 + 1 = 2\) самокат қалды \(\rightarrow\) жеткіліксіз \(\rightarrow\) өтінім өткізіледі.
\(4\) сәтінде үшінші жеткізілім келеді: \(1\) самокат, \([4, 6)\) аралығында әрекет етеді.
\(4\) сәтіндегі өтінім: 1 және 3 жеткізілімдері (екіншісі мерзімі өткен) әрекет етеді \(\rightarrow\) \(1\) (біріншіден) + \(1\) (үшіншіден) қолжетімді \(\rightarrow\) барлығы \(2\) \(\rightarrow\) жеткіліксіз \(\rightarrow\) өтінім өткізіледі.
\(5\) сәтінде төртінші жеткізілім келеді: \(1\) самокат, \([5, 8)\) аралығында әрекет етеді.
\(5\) сәтіндегі өтінім: 1, 3 және 4 жеткізілімдері әрекет етеді \(\rightarrow\) \(1 + 1 + 1 = 3\) қолжетімді \(\rightarrow\) өтінім орындалады.
Нәтижесінде \(1\), \(2\) және \(5\) сәттерінде өтінімдер орындалды, жауап — \(3\).
Пікірлер