ArraySub SPOJ Solution :

Problem Statement :

                      No need to write it here. Instead I'll provide the link.

         

           URL : ArraySub - SPOJ

Constraints :

        n < 10^6

        1 <= k <= n

        0 < ai < 10^6 (Don't assume -ve numbers are there)

IMPLEMENTAION :

        It's easy from the problem to understand that if we use the segmentation trees, the queries can be answered efficiently. Yes there is only a slight modification in the problem statement. It asks you for the contiguous subarray maximum values of length k. If you implement this efficiently, then you will get it accepted in the first attempt itself. 

       All you need to do is to update the internal nodes with the maximum value of their leaf nodes. Usually in a segmentation tree, data are stored in the leaf nodes and their internal nodes are updated according to what the problem asks.

       As usual sticking to the python,this is implemented...

Source Code : IDEONE

       

import sys

sys.setrecursionlimit(10**9+7)

Seg_Tree=[0]*4000010

def Construct_Tree(index,left,right,lists) :

    if left == right :

        Seg_Tree[index] = lists[left-1]

    else :

        Construct_Tree(2*(index),left,(left+right)//2,lists)

        Construct_Tree(2*(index)+1,(left+right)//2+1,right,lists)

        Seg_Tree[index] = max(Seg_Tree[index*2],Seg_Tree[(index*2)+1])

def Answer_Queries(pos,left,right,low,high) :

    if low > right or high < left :

        return False

    elif low <= left and high >= right :

        return Seg_Tree[pos]

    else :

        return max(Answer_Queries(2*pos,left,(left+right)//2,low,high),Answer_Queries((2*pos)+1,(left+right)//2+1,right,low,high))

def main(*args,**kwargs) :

    n = input()

    lists = list(map(int,sys.stdin.readline().split()))

    k = input()

    Construct_Tree(1,1,n,lists)

    i,answer=1,[]

    while n >= i+k-1 :

        answer.append(Answer_Queries(1,1,n,i,i+k-1))

        i+=1

    print " ".join(str(i) for i in answer)

if __name__ == "__main__" :

    main()

That's it. Yes it looks pretty simple but be careful about the input/output. Output contains space between the each numbers.And also be careful in allocating the space for seg_tree.Yes,It costed me several RE in Spoj and still struggling to get out of it though my algo is correct.

If you find any mistake in the implementation,just note it down in the Comment box...HAPPY CODING =D =D =D.