Warhead38's blog

By Warhead38, history, 5 weeks ago, In English,

problem link:https://www.spoj.com/problems/XXXXXXXX/ solution link:https://ideone.com/gh52Zm TLE after 20th test case at spoj. plz help someone.

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Your code is quite hard to read and understand. When you're asking for help, even a small bit of commentary would go a long way.

That said, the comments on the website are clear

MO with update + compression = AC

Try using compression on the stored numbers so you don't need slow accesses to the unordered_map f. Instead it can be replaced by an array that stores the value of each used number.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    but by using array i wont be able to check the count of -ve numbers. also i dont know about compression.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      So, you read the original array and all the queries to start with.

      Take each value that will ever be in the array (both to start or afterwards) and put it into a vector<pair<ll, *ll>> where the first is the number and the second is a pointer back to it. call it compress.

      Run sort() on that array.

      Also make an array to hold your mapping back to the original numbers. call it orig. Now do something like follows:

      int curr = compress[0].first;
      int idx = 0;
      for(int i = 0; i < compress.size(); i++) {
          if(curr != compress[i].first) idx++;
          curr = compress[i].first;
          orig[idx] = curr;
          *compress[i].second = idx;
      }
      

      Now you're guaranteed that each number you might store has a unique id < orig.size(), and you can recover the original value by reading it from orig. Now that all the numbers you're working with are small, you can turn f from a slow map into a fast array. Just remember that instead of cnt += ele, to do cnt += orig[ele] instead.