HackerEarth Harmonic Triplets problem solution

31 July 2024 YASH PAL

In this HackerEarth Harmoni Triplets problem solution, you are given an array A. A triplet is said to be a Harmonic triplet if it satisfies the following conditions :

i < j < k
A[i] <= A[j] >= A[k]

You have to find the harmonic triplet with the maximum value of A[i] x A[j] x A[k]. You are given q queries, wherein each query you are given jth index and you have to find the harmonic triplet with value at jth index which has a maximum product.

HackerEarth Harmonic Triplets problem solution

HackerEarth Harmonic Triplets problem solution.

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

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pp;
typedef pair<pp,pp> ppi;
typedef vector<int> vv;

int st[5000005];
int a[1000005];
ll ans[1000005];

ll build(int s,int e,int i)
{
    if(s==e)
    {
        st[i]=a[s];
        return st[i];
    }

    int mid=(s+e)/2;
    st[i]=max(build(s,mid,2*i+1),build(mid+1,e,2*i+2));
    return st[i];
}

ll query(int s, int e,int l,int r,int i)
{
    if(l<=s && r>=e)
        return st[i];
    if(e<l || s>r)
        return 0;
    int mid=(s+e)/2;
    return max(query(s,mid,l,r,2*i+1),query(mid+1,e,l,r,2*i+2));
}

void update(int s,int e,int val,int idx,int i)
{
    if(idx<s || idx>e)
        return;
    
    st[i]=max(st[i],val);
    if(s!=e)
    {
        int mid=(s+e)/2;
        update(s,mid,val,idx,2*i+1);
        update(mid+1,e,val,idx,2*i+2);
        st[i]=max(st[2*i+1],st[2*i+2]);
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    scanf("%d",&t);
    
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(ans,0,sizeof(ans));
        memset(st,0,sizeof(st));
        
        int n,q;
        scanf("%d %d",&n,&q);
        
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]),ans[i]=1;
        
        for(int i=0;i<n;i++)
        {
            ans[i]=query(0,1000000,0,a[i],0)*a[i];
            update(0,1000000,a[i],a[i],0);
        }
        
        memset(st,0,sizeof(st));
        for(int i=n-1;i>=0;i--)
        {
            ans[i]*=query(0,1000000,0,a[i],0);
            update(0,1000000,a[i],a[i],0);
        }
        
        while(q--)
        {
            int j;
            scanf("%d",&j);
            printf("%lldn",ans[j-1]);
        }
    }
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,q;
ll a[1000005],ans[1000005];
set<ll>s;
set<ll> :: iterator it;
void calc(ll temp,int i)
{
    it=s.lower_bound(temp);
        if(it==s.begin())
        {
            if(*it == temp)ans[i]*=(*it);
                else ans[i]=0;
        }
        else if(it==s.end())
        {
                it--;
                ans[i]*=(*it);
        }
        else
        {
                if(*it == temp)ans[i]*=(*it);
                else
                {
                  it--;
                      ans[i]*=(*it);
                }
        }
        s.insert(temp);
}
int main()
{
    int t;ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>q;
        s.clear();
        ans[0]=ans[n-1]=0;
        cin>>a[0];s.insert(a[0]);
        for(int i=1;i<n;i++)
        {
            cin>>a[i];
            ans[i]=a[i];
        }
        for(int i=1;i<n;i++)
        {
            calc(a[i],i);
        }
        s.clear();
        s.insert(a[n-1]);ans[n-1]=0;
        for(int i=n-2;i>=0;i--)
        {
            calc(a[i],i);
        }
        while(q--)
        {
            int j;
            cin>>j;
            cout<<ans[j-1]<<"n";
        }
    }
    return 0;
}

coding problems