HackerEarth Mancunian And Fantabulous Pairs solution

In this HackerEarth Mancunian And Fantabulous Pairs problem solution First off, some definitions. An array of length at least 2 having distinct integers is said to be fantabulous if the second highest element lies strictly to the left of the highest value. For example, [1, 2, 13, 10, 15] is fantabulous as the second-highest value 13 lies to the left of the highest value 15.

For every fantabulous array, we define a fantabulous pair (a, b) where a denotes the index of the second-highest value (1-indexed) and b denotes the index of the highest value (1-indexed). In the above array, the fantabulous pair is (3, 5). Mancunian challenges you to solve the following problem. Given an array, find the total number of distinct fantabulous pairs overall its subarrays.

HackerEarth Mancunian And Fantabulous Pairs problem solution.

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}



const int N = 1000*1000+5;
int n, arr[N], next_right[N], maxlen[N], next_left[N];
set<int> distinct_;



int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    assert(n >= 1 && n <= 1000*1000);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        assert(arr[i] >= 1 && arr[i] <= 1000*1000*1000);
        distinct_.insert(arr[i]);
    }
    assert((int)distinct_.size() == n);

    stack<int> st;
    for(int i=n;i>=1;i--){
        next_right[i] = -1;
        while(!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        if(!st.empty())
            next_right[i] = st.top();
        st.push(i);
    }

    while(!st.empty())
        st.pop();
    for(int i=1;i<=n;i++){
        next_left[i] = 0;
        while(!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        if(!st.empty())
            next_left[i] = st.top();
        st.push(i);
    }

    for(int i=1;i<=n;i++){
        if(next_right[i] != -1)
            maxlen[next_right[i]-i] = max(maxlen[next_right[i]-i], i - next_left[i]);
    }

    ll ans = 0;
    for(int i=1;i<=n;i++)
        ans += maxlen[i];
    cout<<ans;
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000005
#define ii pair<int,int>
#define ff first
#define ss second
#define ll long long

int arr[MAXN];
int nextBig[MAXN];
int prevBig[MAXN];
int maxi[MAXN];
int n;
ll ans;

void makeNext(){
    int i;
    stack<ii> s;
    for(i=n-1;i>=0;i--){
        nextBig[i] = i;
        while(!s.empty() && s.top().ff < arr[i])
            s.pop();
        if(!s.empty())
            nextBig[i] = s.top().ss;
        s.push(ii(arr[i],i));
    }
}

void makePrev(){
    int i;
    stack<ii> s;
    for(i=0;i<n;i++){
        prevBig[i] = -1;
        while(!s.empty() && s.top().ff < arr[i])
            s.pop();
        if(!s.empty())
            prevBig[i] = s.top().ss;
        s.push(ii(arr[i],i));
    }
}

int main ()
{   
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
    
    makePrev();
    makeNext();

    for(i=0;i<n;i++)
        if(nextBig[i]!=i) 
            maxi[nextBig[i]-i] = max(maxi[nextBig[i]-i], i - prevBig[i]);
    
    for(i=0;i<n;i++)
        ans+=maxi[i];

    printf("%lldn",ans);
    return 0;   
}

HackerEarth Mancunian And Fantabulous Pairs solution

HackerEarth Mancunian And Fantabulous Pairs problem solution.

Second solution

Leave a Reply

Pages

Practice