Need help in a spoj question

I was trying to solve this question https://www.spoj.com/problems/ARRAYSUB/
using sliding window technique.

I am getting wrong answer on test case 5

please help me correct the code.

#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);

    long long int n,k;
    cin>>n;
    
    long long int a[n],i,m=-1,j=0;
    map<long long int,long long int> mp;
    for(i=0;i<n;++i)
       { cin>>a[i];
        
       }

    cin>>k;   
    
    for(i=0;i<k;++i)
      {
          m=max(m,a[i]);
          mp[a[i]]++;
      }
  
     cout<<m<<" ";
     
     for(i=k;i<n;++i)
     {
         mp[a[j]]--;
         if(mp[a[j]]==0)
            mp.erase(mp[a[j]]);
            
         mp[a[i]]++;
         
         auto it=mp.end();
         --it;
         cout<<it->first<<" ";
         j++;
     }
    
    
return 0;

}

Are you erasing elements from your map correctly?

1 Like

multiset would be more helpful

I don’t think so. You cannot blindly ease an element from the set. What if the element that you are erasing has an other occurrence in the current window? You wouldn’t know that if you use a set.

1 Like

Oh sorry, I meant multiset

1 Like

If you look at a multi-set in c++, the implementation is essentially a map :P. It stores a key, and the occurrence as a value. However there is something that you have to keep in mind while using a multiset.

s.erase(3) deletes all occurrences of 3. To delete a single instance:

auto it = s.find(3);
s.erase(it);

IMO, I always avoid multisets, because working with a multiset is not really the same as working with a set. So I generally use a map whenever needed.

There are some subtle differences. More on this here.

2 Likes

Yeah when set and map is combined it becomes multiset. But I kinda like it. :man_shrugging:
Its very short using multiset

Code
for(int i=1;i<=n;i++)
    {
        s.insert(arr[i]);
        if(i>k)
        s.erase(s.find(arr[i-k]));
        if(i>=k)
        v.push_back(*--s.end());
    }
1 Like

Yep, that looks neat. My first thought was to use a BIT xD.

2 Likes

What was your approach?

Can you please tell me what is wrong with the erase part?

yes i solved the problem using multiset.
thank you anyways!.

Nevermind. I don’t think you can do it with a BIT.

@aditya_rajiv Look here to see how to erase something from a map. You pass a ‘key’. Not a value.

Changing this to mp.erase(a[j]); gave me AC, for your code.

1 Like

oh shit what a blunder…so stupid.
thank you !.