Thanks for participating!
The top 5 contestants from this week's contest are:
Great job guys!
Here's the Editorial for the contest. Feedback of any kind is appreciated in the comments.
Tutorial
Solution
Tutorial
Solution
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | cry | 157 |
3 | nor | 157 |
5 | atcoder_official | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
STL #1 Round Editorial
Thanks for participating!
The top 5 contestants from this week's contest are:
Great job guys!
Here's the Editorial for the contest. Feedback of any kind is appreciated in the comments.
Let's store the last moment when somebody gets a tea in the variable $$$lst$$$. Then if for the $$$i-th$$$ student $$$lst ≥ ri$$$ then he will not get a tea. Otherwise he will get it during max($$$lst$$$ + 1, $$$l_i$$$) second. And if he gets a tea then $$$lst$$$ will be replaced with the answer for this student.
[submission:159713776]
Approach 1:
Let's use STL function std::lower_bound()
to solve this problem. First make vector of pair of <Total_Damage,Time_Stamp> and then use the lower_bound()
function to find the smallest Total Damage just greater than or equal to $$$c_j$$$ and then print the Time Stamp corresponding to that damage. Reference for lower_bound()
function
Time Complexity: $$$O(n+m\cdot log(n))$$$
NOTE: This problem could have been solved using binary search but wasn't needed since you know STL.
Approach 2:
First sort the $$$c$$$ array using std::sort()
function (in $$$O(m\cdot log(m))$$$ time) and then iterate through $$$c$$$. Once you find the smallest damage $$$a_i >= c_j$$$ then you know that that $$$c_{j+1} >= a_i$$$. Use this fact to solve the question in $$$O(n+m)$$$ (after sorting) time.
Time Complexity: $$$O(n+m\cdot log(m))$$$
[submission:160223611]
Rev. | Язык | Кто | Когда | Δ | Комментарий | |
---|---|---|---|---|---|---|
en12 |
![]() |
Eren-Jaeger | 2022-06-12 23:40:11 | 1 | (published) | |
en11 |
![]() |
Eren-Jaeger | 2022-06-12 23:39:15 | 47 | ||
en10 |
![]() |
Eren-Jaeger | 2022-06-12 23:37:02 | 11 | Tiny change: ' function `fractal(' -> ' function `fractal(' | |
en9 |
![]() |
Eren-Jaeger | 2022-06-12 23:33:27 | 488 | ||
en8 |
![]() |
Eren-Jaeger | 2022-06-12 23:29:34 | 879 | Tiny change: ')` for $(x1, y1)$ be' -> ')` for $(x_1, y1)$ be' | |
en7 |
![]() |
Eren-Jaeger | 2022-06-12 23:14:00 | 987 | ||
en6 |
![]() |
Eren-Jaeger | 2022-06-12 23:08:48 | 1521 | ||
en5 |
![]() |
Eren-Jaeger | 2022-06-12 23:03:17 | 1923 | Tiny change: 'x + 1, r)$, where by' -> 'x + 1, r)$ , where by' | |
en4 |
![]() |
Eren-Jaeger | 2022-06-12 22:50:10 | 411 | Tiny change: 'nt state. If the to' -> 'nt state. If the to' | |
en3 |
![]() |
Eren-Jaeger | 2022-06-12 22:41:51 | 297 | Tiny change: 'roach 1:\n\nLet's us' -> 'roach 1:\nLet's us' | |
en2 |
![]() |
Eren-Jaeger | 2022-06-12 22:31:42 | 524 | Tiny change: 'in-cpp/)\nNOTE: Th' -> 'in-cpp/)\n\nNOTE: Th' | |
en1 |
![]() |
Eren-Jaeger | 2022-06-12 22:09:47 | 1223 | Initial revision (saved to drafts) |
Название |
---|