# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Name |
---|
Imagine it like a binary tree. Each call to query function generates 2 further recursive calls. The height of tree will be O(logN). So, the complexity for query function will be O(2logN) = O(N). Thus, TLE.
In other code, the binary tree becomes a path of length O(logN) due to single recursive call which reduces complexity of query function to O(logN).
...but why is the query function is being called twice because of the macro? From what i can figure.... the macro gets replaced at compile time into actual code..and hence the query function must run just once
ans = min(ans, query())
changes toans = ((ans>query())?query():ans)
. That's why it is called twice, once for comparison and then for assignment.ah yes!! thanks...i should've noticed that
C/C++ macros are dumb text replacements so expression can be evaluated multiple times if it gets used multiple time. This is one of reasons why use of macros is discouraged in most professional c++ style guide (conditional compiling is an exception). I would also suggest avoiding them to beginners. Saving a few symbols might save some seconds for top participants but will not help beginners become red. The time debugging unexpected macro behaviour would be better spent getting better at algorithms and data structures. At least half the time macro can be replaced with different c++ feature that achieves the same but better.