Tobby_And_Friends's blog

Data Structure Problem: How do I optimize my solution for SPOJ KQUERY2 — K-query II?
By Tobby_And_Friends, history, 8 years ago, In English

I tried to implement the problem using segment tree and multisets. I got a verdict of TLE. How can I optimize my code? Or is there a better solution?

Problem link: http://www.spoj.com/problems/KQUERY2/en/

Solution link: http://ideone.com/gDAmUW

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

Comments Comments (13)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Both N and A[i] are quite small, so maybe something like sqrt decomposition with fenwick tree in each block would pass.

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

    It seems that u will get ~1000 operations for each query with this approach. Idk, mb 2 * 10^8 will pass in 0.85s on spoj

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

You can try using an array instead of the multiset to get O(log^2 N) complexity per query.

Depending on how the multiset is implemented you will get extra O(log N) factor of a big constant.

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

    If I use an array will it not cause me a MLE? I mean I need to create a 2D one. Or am I not getting your idea? If it's not too much of a trouble can you please elaborate a bit?

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

      i believe he ment to do following: in each node of ur seg.tree store sorted array of elements of its subtree instead of multiset. This doesnt work anyway i believe.

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

    If u use array instead of multiset u'll get like O(nlog^2(n)) rep update query, wont u? i mean u'll have to resort arrays all the time.

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

      Oh, I haven't seen the modify operation but the query one.

      → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

your approach is incorrect 

int id = distance(tree[node].begin(), it);

this works in O(n)

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

I think u should use 2-D BIT

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

    Lol the memory limits are so lenient that you don't even need maps — you can literally just do

    short bit[30010][10010];

    and still have over half the memory to spare

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can find the solution here: http://mirror.codeforces.com/blog/entry/18470

→ Reply