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
solution
- push the salaries into a vector
- sort the vector
- use std::unique to remove duplicates
- 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.