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

TLE using segment trees ??? What else can i use ?
Автор suraj021, 9 лет назад, По-английски

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 :)

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится 
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)

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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.

→ Ответить