LightOJ 1093 - Ghajini

// Accepted
// RMQ and RMQ

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

const int mod = 1000007;
const int high = 100003;
const int inf = 1 << 30;

LL ar[high], br[high], treemini[4 * high], treemaxi[4 * high];

void buildmini(int node, int b , int e)
{
    if(b > e) return;

    if(b == e)
    {
        treemini[node] = ar[b];
        return;
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    buildmini(Left, b , mid);
    buildmini(Right, mid+1, e);

    treemini[node] = min(treemini[Left] , treemini[Right]);
}

LL queryForMini(int node, int b , int e , int i, int j)
{
    if(i>e or j<b or b>e) return inf;

    if(b>=i and e<=j)
    {
        return treemini[node];
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    LL p1 = queryForMini(Left, b , mid , i , j);
    LL p2 = queryForMini(Right, mid+1, e , i , j);

    LL res = min(p1, p2);

    return res;
}

void buildmaxi(int node, int b , int e)
{
    if(b > e) return;

    if(b == e)
    {
        treemaxi[node] = br[b];
        return;
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    buildmaxi(Left, b , mid);
    buildmaxi(Right, mid+1, e);

    treemaxi[node] = max(treemaxi[Left], treemaxi[Right]);
}

LL queryForMaxi(int node, int b, int e, int i , int j)
{
    if(i>e or j<b or b>e) return -inf;

    if(b>=i and e<=j)
    {
        return treemaxi[node];
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    LL p1 = queryForMaxi(Left, b , mid , i , j);
    LL p2 = queryForMaxi(Right, mid+1, e , i , j);

    LL res = max(p1, p2);

    return res;
}

int main()
{
    int t, tc=0, n , d, i;
    LL maximumvalue, minimumvalue, maxi=-1;
    sf("%d", &t);

    while(t--)
    {
        sf("%d %d", &n , &d);

        for(i=0; i<n; i++)
        {
            sf("%lld", &ar[i]);
            br[i] = ar[i];
        }

        buildmini(1, 0, n-1);
        buildmaxi(1, 0, n-1);

        maxi = -1;

        for(i=0; i<n; i++)
        {
            if(i+d-1 < n)
            {
                maximumvalue = queryForMaxi(1, 0, n-1, i, i+d-1);

                minimumvalue = queryForMini(1, 0, n-1, i, i+d-1);

                maxi = max(maxi, maximumvalue - minimumvalue);
            }
        }

        pf("Case %d: %lld\n", ++tc, maxi);
    }

    return 0;
}