1 / 5
Apr 2021

I am getting WA again and again can anybody help me?


RMQSQ - Range Minimum Query

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


int mergeTree(int p[] ,int arr[],int n,int l ,int r ,int k)
{
    if(l>r)
        return 0;
    if(l==r)
    {
     p[k]=arr[l];
     return p[k];
    }
    int mid=(l+r)/2;
     p[k]= min(mergeTree(p,arr,n,l,mid,2*k+1),mergeTree(p,arr,n,mid+1,r,2*k+2));
    // cout<<p[k]<<endl;
    return p[k];

}
int getMinimumHelper(int p[] ,int arr[],int n,int l ,int r ,int k,int qs ,int qe)
{
    if( qe<l || qs>r )
        return INT_MAX;


        if(qs<=l && qe>=r)
            return p[k];
    int mid=(l+r)/2;
     return min(getMinimumHelper(p,arr,n,l,mid,2*k+1,qs,qe),getMinimumHelper(p,arr,n,mid+1,r,2*k+2,qs,qe));

}
int getMinimum(int p[] ,int arr[],int n,int l ,int r ,int qs ,int qe)
{

if(qs<l || qe>r)
{
    cout<<"Invalid"<<endl;
    return -1;
}
return getMinimumHelper(p,arr,n,l,r,0,qs,qe);
}
void segmentTree(int p[],int arr[],int n ,int s)
{
for(int i=0;i<s;i++)
{
    p[i]=INT_MAX;
}
    p[0]=mergeTree(p,arr,n,0,n-1,0);
}

int main()
{
    int Size,q;
   // cout<<"enter size of array and number of query"<<endl;
    cin>>Size;
   // Size=6;
    int arr[Size];
    //cout<<"enter array elements"<<endl;
    for(int i=0;i<Size;i++)
        cin>>arr[i];


    int n=2*floor(pow(2,ceil(log2(Size)))+0.5)-1;
   // cout<<n<<endl;
    int root[n];

            //int* root=new int[n];
    segmentTree(root,arr,Size,n);
/*for(int i=0;i<n;i++)
{
    cout<<root[i]<<" ";
}*/
int l,r;
char c;


    cin>>l>>r;
   
         cout<<getMinimum(root,arr,n,0,Size-1,l,r)<<endl;
   


}
  • created

    Mar '21
  • last reply

    Jun '21
  • 4

    replies

  • 737

    views

  • 3

    users

  • 4

    likes

  • 1

    link

I can’t see where you read in q, did I miss it?

btw, when posting code, it’d help preserve the formatting if you put three back ticks ``` on a line by themselves both before and after the code.

Thanks
My solution is accepted now.
I am new so did not know about ``` but now understood
Thanks once again
can you solve one more doubt ?

18 days later

@garvit Oh i am also doing this recently again and again but nothing happened. Thanks for sharing this i will recover it.:heart_eyes:

1 month later