In the problem D of recent Edu round, I used binary search to solve the problem, but i'm not able to figure out where the TLE is, please help me find out.
# | 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 | 163 |
2 | maomao90 | 160 |
3 | adamant | 156 |
3 | nor | 156 |
5 | atcoder_official | 155 |
5 | -is-this-fft- | 155 |
7 | maroonrk | 153 |
7 | cry | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
In the problem D of recent Edu round, I used binary search to solve the problem, but i'm not able to figure out where the TLE is, please help me find out.
Name |
---|
For this problem, O(nlogn) with bad constant factor could TLE. However, if you add this line of code right after you declare main(): ios_base::sync_with_stdio(false); cin.tie(NULL); Using the above code will make the input factor and can make the code significantly faster.
Take a look at my submission of your code with the added line: 277182525 It gets 1842ms with AC.
Feel free to also look at my O(n) solution which passes relatively comfortably (since 1842 ms is still a lot): 276595217
Note that the pragma that I include in the top could also make your code faster. These things might be a good idea for you to include in your template.
Hope this helps!
Thank you so much for this! Will make sure about this in the future, also the O(n) solution is great too! Thanks a lot!!
Do not use map. Instead use vector of vector for the mp variable.