Need help in a spoj question

help
1

I was trying to solve this question SPOJ.com - Problem 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;

}

2

Are you erasing elements from your map correctly?

1 Like
3

multiset would be more helpful

4

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
5

Oh sorry, I meant multiset

1 Like
6

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
7

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
8

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

2 Likes
9

What was your approach?

10

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

11

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

12

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
13

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