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

Segment tree
Автор rahulpadhy, история, 9 лет назад, По-английски

Hi, I am new to segment trees. I am getting RE for this SPOJ question and I am unable to find out the mistake in my code. So, can you guys please help ?? Here's the link to the question... http://www.spoj.com/problems/GSS1/

And, here's my solution.. http://pastebin.com/dtKe4rx4

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

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

Your logic is wrong.

Take this test:

3
2 -1 2
1
1 3

Your output: 4
Answer: 3

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Answer should be 4 because we need to find the maximum possible sum obtained from the elements in the specified indices(2 + 2 = 4)... But my main concern is as to why I am getting RE for this question...

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can't do 2 + 2 because there's a -1 in between. Read the problem statement. They want maximum contiguous subarray sum. I solved it, I know what I'm talking about.

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      As for the runtime error, check out this test:

      3
2 -1 2
1
3 3

      You're not exiting the query function when your current range is completely outside the query range. You should do something like: 

      if (start > r || end < l)
     return 0;
      → Ответить