gastivy's blog

By gastivy, history, 6 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for the specified constraints, your solution won't work. Try reading about segment trees.