Блог пользователя lazy_wallflower

Why is my code giving a TLE?
Автор lazy_wallflower, история, 4 часа назад, По-английски

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.

276695555 2004D - Colored Portals

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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!

→ Ответить
  • »
    »
    2 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!!

    → Ответить
»
23 минуты назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do not use map. Instead use vector of vector for the mp variable.

→ Ответить