CSES Salary Queries

Why is coordinate compression combined with a BIT to slow in https://cses.fi/problemset/task/1144/

1 Like

It should not be too slow unless you’re using Java. Can you send your submission?


My O(NlogN) Java solution (with coordinate compression + BIT) for this same problem got TLE on a few cases. I’ve heard that CSES’s judge is a bit slow, so should I be concerned about this or should I consider it as AC and move on?

It’s faster to do everything without maps (sort arrays instead).

1 Like

i think you should consider to

  1. push the salaries into a vector
  2. sort the vector
  3. use std::unique to remove duplicates
  4. and using lower_bound and upper_bound to find the index.
    Then using a BIT to maintain the salaries gives you AC

For Java solution, it’s fast enough to AC with sort + coordinate compression + BIT.

@dongliu0426 I am trying to use segment tree. Won’t the indices change when you remove duplicates?

Say I sort original salaries and put them in segment tree. Now if I use the unique vector to find indices, it would give wrong answer as there might be duplicates in my segment tree.

1 Like

What about removing duplicates and then putting them into a segment tree?

Ohh wait so I should put count of numbers in the range_sum segment tree and then binary search numbers to find the indices to range sum over? Seems like that could do the job.

@Benq Also, I went to your codeforces page. I haver seen so many good things in a single web page.