yshkpr's blog

AtCoder Beginner Contest 158 Problem D
By yshkpr, history, 5 years ago, In English

Please help me to find why TLE is coming in my solution. Solution Link- https://atcoder.jp/contests/abc158/submissions/10968142

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution is brute, you are literally doing what the query asks you to do. In particular, lines $$$46$$$ and $$$47$$$ are too slow ( they are $$$O(|a|)$$$ which can be $$$O(N)$$$ ). So, the whole complexity becomes $$$O(Q*N)$$$.

You need to solve the problem, without updating the original string each time ( atleast I don't know a fast way to update the original string after each query ).

→ Reply