alyosha's blog

Help in CSES Salary Queries.
By alyosha, history, 18 months ago, In English

Hello, I was solving Salary Queries in CSES. I coded a BIT solution with complexity O(nlog^2(x)) solution but it doesn't pass all the testcases as it takes approx 3.5 seconds to run. Here's the link to the code https://cses.fi/paste/af0c566bad71c1a7c62bff/ . I don't want to use pre-code data-structures as I want to practice implemtation as well. All the solution i found on the internet contains unordered_set already implemented. Any suggestions are welcome.

Thanks

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You may consider using coordinate compression for this problem. You should compress the values of a[i], b[i], p[i], x[i]. Now, the values are up to 8 * 10^5 instead of 1e9. You can do a normal BIT there instead of that one which is implemented with map

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

    Thanks a lot for your reply. Yes, I thought of that, but it felt like cheating, cause the testcases are supposed to be processed in a online sense right. Rather than storing all the values of a[i], b[i], p[i], x[i] and then compressing them. What I mean is to compress the values of p[i], x[i] I need to know all the possible values which i might encounter during answering the queries, first then sort them and map them from 0, 1, 2... Or is there some other way to compress them in a online way?

    → Reply
    • »
      »
      »
      18 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Hope what I meant was clear. One solution I was thinking was implement something similar to a ordered set from scratch, but i can't find any resource that might help me in same.

      → Reply
    • »
      »
      »
      18 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I don't think that there's a way to make compressions online. But there is a solution which will make all the queries online while there's no need for compression: using Implicit Segment Tree. It can support operations on segments with r <= 1e9.

      → Reply
      • »
        »
        »
        »
        18 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Thanks a lot, It was my first time hearing about that variation of segment tree and it's exactly the data structure I needed. Thanks again for the help

        → Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Instead of using a map use a vector of size $$${4\times 10^5}$$$ , this supposes that the array reached maximum size and all of its values are distinct , also all the values in the queries to be distinct.

read all queries and store them in some array called queries for example , store the values of the array and the values in the queries in some vector so you can do a coordinate compression on the array and the query values as well , then using the BIT with the prior declared vector will be feasible.

This makes the time complexity $$${O(log(n))}$$$ per query with some logarithmic pre processing.

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks for the reply, Yes, we can solve it like that, But storing all the queries makes solving the problem in an offline way. I wanted to have an online solution which I believe is the way CSES problems are meant to be solved.

    → Reply