In this HackerEarth Haunted problem solution, The king of ghosts is really disappointed when he sees that all the human beings on Planet Earth have stopped fearing the ghost race. He knows the reason for this. The existing ghost race has become really lazy and has stopped visiting Planet Earth to scare the human race. Hence, he decides to encourage the entire ghost race into scaring the humans by holding a competition. The king, however, never visits Planet Earth.

This competition will go on for N days. Currently, there are a total of M ghosts (apart from the king) existing in the ghost race such that :
- The youngest ghost is 1 year old.
- The oldest ghost is M years old.
- No two ghosts have the same age.
- The age of each and every ghost is a positive integer.

On each day of the competition, ghosts have to visit Planet Earth to scare people. At the end of each day, a "Ghost of the Day" title is awarded to the ghost who scares the most number of humans on that particular day. However, the king of ghosts believes in inconsistency. Once this title has been given, the ghost who has won the most number of such titles until that particular moment is presented with a "Consistency Trophy". If there are many such ghosts, the oldest among them is given the trophy. Note that this "Title Giving" and "Trophy Giving" happens at the end of each day of the competition.

You will be given the age of the ghost who won the "Ghost of the Day" title on each day of the competition. Your job is to find out the age of the ghost who was awarded the "Consistency Trophy" on each day of the competition.


HackerEarth Haunted problem solution


HackerEarth Haunted problem solution.

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int a[100100]={0};
int main()
{
    priority_queue<pair<int,int> >P;
    int n,i,x,m;
    int k=0;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        if(mp.count(x)==0)
        {
            mp[x]=k;
            a[k]++;
            k++;
        }
        else
        {
            a[mp[x]]++;
        }
        P.push(make_pair(a[mp[x]],x));
        printf("%d %d\n",P.top().second,P.top().first);
    }
    return(0);
}

Second solution

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define FOR(i,lb,ub) for(i=lb;i<=ub;i++)
#define RFOR(i,ub,lb) for(i=ub;i>=lb;i--)
#define FORS(it,v) for(it=v.begin();it!=v.end();it++)
#define int long long
#define st_clk double st=clock();
#define end_clk double en=clock();
#define show_time cout<<"\tTIME="<<(en-st)/CLOCKS_PER_SEC<<endl;
int gcd(int a, int b) { return b?gcd(b,a%b):a; }
using namespace std;
map<int,int> mm;
void solve()
{
    int n,m, cnt=0, val;
    cin>>n>>m;
    assert(n>=1 && n<=100000);
    assert(m>=1 && m<=1000000000ll);
    while (n--)
    {
        int x,cc;
        cin>>x;
        assert(x>=1 && x<=1000000000ll);
        if (mm.count(x)==0)
        {
            mm.insert(make_pair(x,1));
            cc=1;
        }
        else
            cc = ++mm[x];
        
        if (cnt<cc)
        {
            cout<<x<<" "<<cc<<endl;
            cnt = cc;
            val=x;
        }
        else if (cnt==cc)
        {
            cout<<max(x,val)<<" "<<cc<<endl;
            val = max(val,x);
        }
        else
        {
            cout<<val<<" "<<cnt<<endl;
        }
    }
}
main()
{
    st_clk
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}