sazzad8867's blog

What problem in this code related segment tree

By sazzad8867, 9 years ago, In English

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???

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply