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 :
  1. i < j < k
  2. 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("%lld\n",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;
}