| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Problem:https://codeforces.me/contest/1287/problem/B
hg333, problem in memory allocations on heap. Easy fix with runtime
1075ms.dmkozyrev, that works. But the time complexity O(n*n*k) should not be affected by such things, still they can cause a TLE.
hg333, you have $$$n^2\cdot \log(k)$$$ queries to heap manager. Of course, this is TLE, heap manager works very slow and total runtime of these queries greater than 2 seconds. Try to read how heap manager works.
I understand that changing function argument from :
f ( string s ) to f ( string &s ) makes difference.
Is there something beneficial to even add "const" before it and writing f ( const string &s ) with respect to execution time ?
It guarantees that you are not allowed to change arguments in function body, but it is not significant improvement for runtime, only
0.3s.Main part is
static string a; a.clear();: decreases runtime by1.7s.Are you sure the OP's original code allocated objects on the heap? His string variable is declared with automatic storage duration (i.e. local variable with no new keyword). I think it is allocated on the stack.
std::string class has a pointer to allocated on the heap memory, if string isn't small
Where’s the source of this? I would like to read more.
I think this is just common knowledge, probably mentioned in good C++ books. C++ objects have compile-time constant sizes, so
std::stringmust store longer strings separately on the heap.This is example. When we tried to add char 'p', operator new was called for the first time. And yes, looks like for original problem not $$$n^2 \cdot \log(k)$$$ calls, but only $$$n^2$$$ queries to heap manager.
It can be found in source code of C++ STL, I think.
I read through the STL docs. I think the same can be said for any STL container such as vector, set, list, etc. They all have pointers to their underlying elements (whose space is dynamically allocated by an allocator).
So I guess the lesson here is, for a function that has many local variables which are STL containers and is called many times, always put a static storage specifier in front of those variables?
For competitive programming there is a two another solutions: 1) create own memory buffer and rewrite operator new/delete: solution, 1169 ms; 2) use C++17 monotonic buffer resourse (memory pool), when it will be supported by codeforces. Because your program will end by 2-3 seconds and you can ignore memory releases.