You are not logged in. Please login at www.codechef.com to post your questions!

×

D-Query Segmentation Fault Bug

I tried solving D-Query http://www.spoj.com/problems/DQUERY/ using Mo's algorithm, but my code keeps giving Segmentation Fault, have been trying for the past hour and still can't debug it. Would appreciate it if someone can help. Thanks. Here is my code. http://ideone.com/o9qLUW

asked 14 Jun '17, 16:34

ravenclaws1's gravatar image

3★ravenclaws1
283
accept rate: 100%

edited 14 Jun '17, 16:41


Your solution looks correct, but just three comments:

  1. C++ requires compare function to be transitive for sort to work (see reference). Try replacing <= with < in your second code block, this will remove seg fault.
  2. Though that removes segfault, your solution will TLE because your compare function looks expensive. For example, you are calculating sqrt(n) every time, which is an extra $\Theta(log N)$ factor. Try caching that into a variable.
  3. Lastly, try passing const pair<ii, ll>& instead so that you don't pass-by-value the big pairs during sort. This link in stackoverflow can explain why constant references are faster.

I believe these last steps will be enough to get your code to pass :)

link

answered 14 Jun '17, 18:08

hikarico's gravatar image

5★hikarico
1.9k1515
accept rate: 28%

edited 14 Jun '17, 18:13

1

Thank you so much it finally worked. Never thought the compare function would be the main culprit.

(14 Jun '17, 18:29) ravenclaws13★

One observation that i made is that,

query[i].se is of type ll

whereas you are accessing index ans1[query[i].se] which wont be accessible if query[i].se is of range ll and ans1's index only last till 200004 (as you have declared initially).

Try this and let me know :)

link

answered 14 Jun '17, 16:48

godslayer12's gravatar image

1★godslayer12
419210
accept rate: 7%

Sadly doesn't work, the number of queries never go into ll range to begin with.

(14 Jun '17, 16:51) ravenclaws13★

Okay thanks for the check, meanwhile I'll check other factors.

(14 Jun '17, 16:52) godslayer121★

Let the 1st query be 1 3,then initially your curL=0 and you are accessing cnt[a[curL]] but you are taking input as 1-based and hence a[0] would be some garbage value.You have declared cnt array of size 1000005.If a[0] is greater than 1000005 then you are going out of bounds which will result is segmentation fault.

BTW,here is my accepted solution if you have any doubt feel free to comment https://pastebin.com/mRqp9ha1

link

answered 14 Jun '17, 16:56

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

It still gives segmentation fault after I initialized a[0] as 0, also since I have declared it globally it should have already been 0 initially to begin with.

(14 Jun '17, 17:02) ravenclaws13★

try to compare your code with my code

(14 Jun '17, 17:07) hruday9684★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×595

question asked: 14 Jun '17, 16:34

question was seen: 308 times

last updated: 14 Jun '17, 18:29