Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

brdy's blog

Strange segfault on SPOJ KQUERY
By brdy, history, 7 years ago, In English

Here is my AC code: https://hastebin.com/ewobuzater.cpp

It uses offline BIT + sorting.

Here is the strange thing: que[200001] works perfectly fine, but if you change it to que[200000] it will segfault. However, it is zero based indexing and q is at max 200000.

Can anyone think of a case where que[200000] faces out of bound access?

Tags bug
  • Vote: I like it
  • +2
  • Vote: I do not like it

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

Since I am new to this programming will you please explain your solution?

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

    que[] stores the queries

    The idea behind my solution is that instead of solving for each query individually, we sort them in decreasing order of k.

    Now we can change this problem into:

    Which values are greater than k?

    Think about a binary array:

    1 means that the number in the i'th position is greater than k, and 0 means it is not.

    How to find how many is greater from position [i,j]?

    We use some data structures such as segment tree/BIT which gives us range sum in O(logn) and allows us to set a position to 1 in O(logn).

    We can make the observation that if a > b and the value v > a, then v > b.

    Thus, once we go from a higher k to a lower k, the values greater than the higher k will also be greater than the lower k. This is why we sort it in decreasing order.

    We query [l,r] like prefix sums in the bit to count which ones are greater.

    Since queries are not in the order they came in we need another array to store answers.

    Complexity is O(q + nlogn)

    Solution is very similar to classical problem of counting inversions with BIT + sorting.

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

Your operator< returns true for equal elements. sort assumes this is not the case to save some out-of-bounds checks; the extra que element is probably acting as a sentinel. You shouldn't need the extra position if you replace the implementation by return one.k > two.k.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thanks, I tried that and it works.

    → Reply