# Help in solving MSTICK problem. Only 3 testcases succesful submission doing it using sparse table

### My code

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
int n;
cin>>n;
int arr[n];

for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int q;
cin>>q;

int k=log2(n);
int st[k+1][n];
int st1[k+1][n];
copy(arr,arr+n,st[0]);
for(int i=1;i<=k;i++)
{
for(int j=0;j+(1<<i)-1<n;j++)
{
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
copy(arr,arr+n,st1[0]);
for(int i=1;i<=k;i++)
{
for(int j=0;j+(1<<i)-1<n;j++)
{
st1[i][j]=max(st1[i-1][j],st1[i-1][j+(1<<(i-1))]);
}
}
while(q--)
{
int i,j;
cin>>i>>j;
int m=log2(j-i+1);
double ans1=min((double)st[m][i],(double)st[m][j-(1<<m)+1]);
double ans2=max((double)st1[m][i],(double)st1[m][j-(1<<m)+1]);
ans2=(ans2-ans1)/2.0;
double ans3=0;
double ans4=0;
if(i>0)
{
int f=log2(i);
ans3=(double)max((double)st1[f][0],(double)st1[f][i-(1<<f)]);
}
if(j<n-1)
{
int f=log2(n-1-j);
ans4=max((double)st1[f][j+1],(double)st1[f][n-(1<<f)]);
}

double extra=max({ans2,ans3,ans4});
double final=extra+ans1;
cout<<fixed<<setprecision(1)<<final;
}

return 0;
}

``````

Problem Link: MSTICK Problem - CodeChef

@ankush_86
actually its a basic question of advanced data structure named segment tree.
so to make it fully acceptable to have to implement segment tree only.