1093 - Ghajini

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1093

Solution :

#include<bits/stdc++.h>

#define mix 100002

using namespace std;


int arr[mix];

struct Node
{
    int mn;
    int mx;
}  tree[mix*4];



void init(int node, int b,int e)
{

    if(b==e)
    {
        tree[node].mn=arr[b];
        tree[node].mx=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node].mn=min(tree[left].mn,tree[right].mn);
    tree[node].mx=max(tree[left].mx,tree[right].mx);

}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.mn=1000000000;
        temp.mx=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);


    Node p3;
    p3.mx=max(p1.mx,p2.mx);
    p3.mn=min(p1.mn,p2.mn);

    return p3;
}




int main()
{


    int t,n,d;
    Node temp;
    int ans;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d%d",&n,&d);

        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);

        init(1,1,n);

        ans=0;

        for(int i=1;i+d-1<=n;i++)
        {
           temp=query(1,1,n,i,i+d-1);
           ans=max(ans,temp.mx-temp.mn);

        }
        printf("Case %d: %d\n",ca,ans);
    }
}