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

Автор gastivy, история, 3 года назад, По-английски

This is a very simple code so I didn't expect it to take more than 1000 ms. How could I optimize it? https://codeforces.com/contest/380/submission/116189186

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Your time complexity is O(m*n). That's why TLE!!

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

your code can run at most n*m operations where n is the length of the string and m is the number of queries. since you loop from l to r a total of m times, this can go to at most 10^11 operations which will tle.