suraj021's blog

TLE using segment trees ??? What else can i use ?
By suraj021, 9 years ago, In English

I solved 380C - Sereja and Brackets using segment tree for logarithmic time complexity , but my my solution got TLE 11267626 for some test case . I want to ask if there is something wrong with my implementation or i have to use some other data structure ? P.S positive responses will be appreciated :)

UPD: Accepted: 11271890 :)

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it 
void build( string str, int id, int l, int r ){

if you write it this way string str will be copied each time you call the build function, so total complexity is O(n^2).

You should change it to

void build( string& str, int id, int l, int r ){

P.S 11267959 Accepeted by changing only this char)

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It is just my personal opinon, but I think you should learn more basic concepts before segment tree. My suggestion is to learn better more basic concepts, then, after that, you should learn harder concepts.

→ Reply