RPLN - Negative Score - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : RPLN

👉 Hint : Build Segment Tree and query for every text case

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
ll st[4*100002];
ll arr[100002];
void build(int ind,int l,int r)
{
    if(l==r)
    {
        st[ind]=arr[l];
        return;
    }
    int m=(l+r)/2;
    build(2*ind+1,l,m);
    build(2*ind+2,m+1,r);
    st[ind]=min(st[2*ind+1],st[2*ind+2]);
}
 
ll query(int ind,int l,int r,int ql,int qr)
{
    if(l>qr || r<ql)
        return LONG_MAX;
    if(ql<=l && r<=qr)
        return st[ind];
    int m=(l+r)/2;
    return min(query(2*ind+1,l,m,ql,qr),query(2*ind+2,m+1,r,ql,qr));
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    for(int j=1;j<=t;j++)
    {
        int n,q,ql,qr;
        cin>>n>>q;
        for(int i=1;i<=n;i++)
            cin>>arr[i];
        build(1,1,n);
        cout<<"Scenario #"<<j<<":"<<endl;
        while(q--)
        {
            cin>>ql>>qr;
            cout<<query(1,1,n,ql,qr)<<endl;
        }
 
    }
}

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.