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

What problem in this code related segment tree

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

http://www.spoj.com/problems/DQUERY/en/ I tried to solve this problem with divide and conquer.

But in spoj verdicts is segmentation fault. Here is my code.... http://ideone.com/8g7Lyl

Isn't complexity O(nlogn) in total???

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

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

This can be done by divide and conquer. You need to process offline query in this question

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

    In offline how?? can you give me hints or source code??

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

      Well for that you have to sort input and query together . Give the input higher priority . whenever you encounter there is an input operation check if this number previously found or not . If so then change the value to 0 on that point and give one to your update position . And for query just normal segment tree sum .

      for better understanding you can check my code here

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

        btw you are using cin/cout . you can surely get TLE for that . change it to scanf/printf for safety .

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

First. To remove the Segmentation Fault just change the visited array's size to 1000000. Secondly, your code is still O(N*M), so it will get TL-e.

→ Ответить