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

Автор ed1d1a8d, 12 лет назад, По-английски

I'm having trouble figuring out what is wrong with my code. It gets WA on test case #9. Some pointers (*no pun intended*) or advice would be appreciated.

Here is a link to my code: http://ideone.com/vcCrHZ

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

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

In your query function , you are always merging the two children nodes data. This is wrong , because one child's interval doesn't necessarily intersect with the query interval. So , changing your query function to the following yields ACCEPTED. Congratulations :-)


segment query(int n, int b, int e, int x, int y) { if(b > e || b > y || e < x) return segment(MIN_VALUE, MIN_VALUE, MIN_VALUE, MIN_VALUE); else if(x <= b && e <= y) return tree[n]; segment A = query(2*n, b, (b+e)/2, x, y); segment B = query(2*n+1, (b+e)/2+1, e, x, y); if(A.tMax == MIN_VALUE) /* Is A completely irrelevant ? Ignore it ! */ return B; if(B.tMax == MIN_VALUE) /* Is B completely irrelevant ? Ignore it ! */ return A; /* We know for sure that at least one of segments A , B is relevant to the query interval , otherwise we would have exited the recursion by the first line in this function */ return merge(A , B); /* Both A and B are relevant for the query interval , Merge Them ! */ }