599C. Day at the Beach - Codeforces Solution C++

➤  Problem Link : 599C. Day at the Beach 

✅ C++ Solution :

 #include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int main()
{
  int n;
  cin>>n;
  ll arr[n+1];
  ll pos[n+1];
  map<ll,int> freq;
  for(int i=1;i<=n;i++)
  {
    cin>>arr[i];
    freq[arr[i]]++;
  }
  auto it = freq.begin();
  auto it2 = it;
  it2++;
  for(;it2!=freq.end();it++,it2++)
    {
    
    it2->second+=it->second;
    
}
  for(int i=n;i>=1;i--)
  {
    pos[i]=freq[arr[i]];
    freq[arr[i]]--;
  }
 
  int ans=0;
  ll mx=0;
  for(int i=1;i<=n;i++)
  {
    mx=max(mx,pos[i]);
    if(i==mx)
      ans++;
  }
  cout<<ans;
 
 
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.