POJ 2823 Sliding Window

昨日の夜POJ落ちてたが復旧していた。

SegmentTreeつかわなくてもできそうだが練習のため使用。

LanguageをG++ではTLEになったがC++にしたら通った。
POJの闇である。

#include <cstdio>
#include <climits>
#include <algorithm>
#include <utility>
#include <iostream>

//http://poj.org/problem?id=2823

using namespace std;

typedef pair<int,int> P;

int t[2100000];
int t2[2100000];
P ans[1000002];


int n,kn;

void init(){
    n = 1;
    while(n < kn)n *= 2;

    for(int i = 1;i < n * 2 - 1;i++){
	t[i] = INT_MIN;
	t2[i] = INT_MAX;
    }

}



void add(int a,int b){
    a += n - 1;
    t[a] = b;
    t2[a] = b;
    while(a > 0){
	a = (a-1) / 2;
	t[a] = max(t[a*2+1],t[a*2+2]);
	t2[a] = min(t2[a*2+1],t2[a*2+2]);
    }
}




P get(int a,int b,int v,int l,int r){
    if(a >= r || b <= l)return P(INT_MIN,INT_MAX);
    if(a <= l && r <= b)return P(t[v],t2[v]);
    else{
	P vl = get(a,b,v*2+1,l,(l+r)/2);
	P vr = get(a,b,v*2+2,(l+r)/2,r);
	return P(max(vl.first,vr.first),min(vl.second,vr.second));
    }
}


int main(){
    int k;

    while(cin >> kn >> k){
    init();
    for(int i = 0;i < kn;i++){
	int tmp;
	scanf("%d",&tmp);
	add(i,tmp);
    }
    for(int i = 0;i < kn-k+1;i++){
	ans[i] = get(i,i+k,0,0,n);
    }
    for(int i = 0;i < kn-k+1;i++){
	printf("%d ",ans[i].second);
    }



    printf("\n");


    for(int i = 0;i < kn-k+1;i++){
	printf("%d ",ans[i].first);
    }
    printf("\n");

    }


return 0;
}