Return count of numbers with freq greater than some queries after performing instructions

Question

Recently I was working on a problem and I could not solve it within time constraints. The question is as follows:

Problem:
Bob currently has N empty stacks numbered from 1 to N. He does the following M times: Select 2 two numbers L and R and add one stone to each of the stacks [L,L+1,...R] At the end of these M operations, he would like to answer Q queries: How many of the stacks have at least H stones in them?

Input Format

First line contains N - number of stacks.

Second line contains M - number of operations.

Each of the next M lines consists of two space separated integers L and R.

Followed by integer Q - number of queries.

Each of next Q lines contain a single integer H.

Constraints: 1 ≤ N ≤ 1000000, 1 ≤ M ≤ 1000000, 1 ≤ L ≤ R ≤ N, 1 ≤ Q ≤ 1000000, 1 ≤ H ≤ N,

My approach was as follows:

int main(){
    int n, m, l, r, q, h;
    cin >> n >> m;
    
    vector<int>nums(n,0);

    // processing vector based on instructions
    for(int i=0; i<m; i++){
        cin >> l >> r; 
        for(int j=l-1; j<r; j++)
            nums[j]++;
    }
    //storing freq in map
    map<int, int, greater<int>>count;
    for(auto x: nums)
        count[x]++;
   
    // getting no. of queries
    cin >> q;
    vector<pair<int, int>>queries(q);
    for(int i=0; i<q; i++){
        cin >> h;//query height
        queries[i] = make_pair(h, i);
    }
    
    sort(queries.begin(), queries.end(), greater<int>());
    
    vector<int> res(q,0);
    
    int q_index=0;
    int c = 0;
    for(auto&[key, val]:count){
        while(k<q && key < queries[q_index].first){
            res[queries[q_index].second] = c;
            q_index++;
        }
        c+=val;
        if(k == q){
            break;
        }
    }
    
    for(int x: res)cout << x << endl;
    return 0;
}

This works but fails for large test cases. What should be the approach to solve problems like these? TIA!

This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Nov 08 '20 at 21:30
You're not meant to literally translate the description into code, you're meant to think about the problem and figure out a way to achieve the same result in a less computationally expensive way. This one seems pretty easy, you just have to accept that there's no non-algorithmic trick (e.g. micro-optimization) that will make this fast enough. — EOF, Nov 08 '20 at 21:45

score 0 · Answer 1 · answered Nov 09 '20 at 18:57

The main problem might be the std::map in addition to your O(N^2) loop.

Totally untested code

  int main(){
    int n, m, l, r, q, h;
    cin >> n >> m;
    
    vector<int>nums(n,0);

    // processing vector based on instructions
    for(int i=0; i<m; i++){
        cin >> l >> r; 
        nums[l-1]++;
        nums[r-1]--;
        // saving O(N^2)
        //for(int j=l-1; j<r; j++)
        //    nums[j]++;
    } // O(N) down from O(N^2)

    //storing freq in map --- This costs O(N K + N lg N) but the K is crushing as its allocations
    //map<int, int, greater<int>>count;
    //for(auto x: nums)
    //    count[x]++;
    
    // add up the real height for each stack
    std::partial_sum(nums.begin(), nums.end(), nums.begin()); // O(N)
    std::sort(nums.begin(), nums.end()); // use radex sort instead if timelimit exceeded
    
    // getting no. of queries
    cin >> q;
    //vector<pair<int, int>>queries(q);
    vector<int>queries(q);
    for(int i=0; i<q; i++){
        cin >> h; //query height
        queries[i] = h;
    }
    
    vector<int> res(q,0);

    std::transform(queries.begin(), queries.end(), res.begin(), [&](int q){
      auto i = std::lower_bound(nums.begin(), nums.end(), q); // binary search O(lg N)
      return std::(i, nums.end());
    } // O(N lg N)
    
    for(int x: res)cout << x <<  "\r\n";//endl; // nevar use endl unless you really need it.
    return 0;
  }

Add some const, constexp etc. to make it potentially better.

Radex sort is O(N) but the K for startup is problematic, and the code to write it is none trivial.

A good question is if your solution of sorting the queries and then placing it in the correct order by using .second is better.

Return count of numbers with freq greater than some queries after performing instructions

1 Answers1