9도 OJ 1344: 콜라병 전시회(DP)

시간 제한: 1초
메모리 제한: 32메가
특수 판제:아니오
제출: 430
해결
제목 설명:
모두가 알다시피 JOBDU 산하의 JOBCOLA는 문명 전 세계의 유명한 콜라 제조업체다. 다른 콜라회사와 달리 JOBCOLA콜라는 콜라의 맛으로 유명한 것이 아니라 색다른 포장병으로 소비자들의 흥미를 끌고 있다.JOBCOLA콜라가 설립된 지 100주년이 되는 날, 회사는 여러 해 동안 생산한 콜라병을 모아 콜라병 전시회를 열어 회사의 문화적 품위를 높이려고 한다.그러나 전시장 크기에 따라 일부 병만 전시할 수 있다.JOBDU 이사회와 전시 청부업체의 협상을 거쳐 전시에 사용할 연속적인 병을 선정하는 동시에 최고의 미학적 감각을 얻기 위해 전시된 병 중 가장 높은 병과 가장 낮은 병 사이의 높이는 k를 초과해서는 안 된다.
너에게 주어진 임무는 상술한 요구를 충족시키는 가장 긴 병 서열을 골라 이사회에서 선택하도록 하는 것이다.
입력:
각 테스트 사례는 두 줄로 구성됩니다.
첫 번째 행위는 두 개의 정수, n과 k이다. 그 중에서 n은 선택할 병의 개수를 대표하고 k는 선택한 병 중 가장 높은 병과 가장 낮은 병 사이의 최대 격차이다.여기서 1 <=n <=10
5, 0 <= k <= 10
6.
두 번째 줄은 n개의 정수를 포함하고 모든 정수는 병의 높이(단위는 마이크로미터)를 대표하며 모든 병은 이미 생산 연대에 따라 예로부터 지금까지 순서를 정했다는 것을 알고 있다.
출력:
모든 테스트 사례에 대응하여 출력의 첫 줄은 두 개의 정수 a, b를 포함한다.그 중에서 a는 조건을 만족시키는 병의 개수를 대표한다.b는 몇 개의 그룹이 이런 선택 방안을 가지고 있는지를 대표한다.다음에 b줄을 출력한다. 줄마다 두 개의 정수 s, e(1<=s, e<=n)를 포함한다. 그 중에서 s는 선택한 a병 중 가장 오래된 병의 하표를 대표하고 e는 이 방안에서 최근에 생산된 병의 하표를 대표한다.주의: 여러 방안이 있으면 s에서 큰 순서로 출력합니다.s가 같으면 e의 크기에 따라 출력합니다.
샘플 입력:

3 2
13 12 10

샘플 출력:

2 2
1 2
2 3

아이디어:
사실 나는 AC가 없어서 사고방식에 문제가 있다.나중에 시간 내서 다시 AC.남의 코드부터 붙여.
코드:

//ac code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;


int height[100009];
int n, k;
int h[100009][20];
int l[100009][20];
int exp2(unsigned x);
int getmax(int x, int y);
int getmin(int x, int y);
int Ok(int len);
int rx[100000];
int ry[100000];
int main(){
        while(cin>>n>>k){
                for(int i= 0; i< n; ++i){
                        scanf("%d", height+i);
                }
                for(int i= 0; i< n; ++i){
                        h[i][0]= i;
                        l[i][0]= i;
                }
                int x= exp2(n);
        //RMQ
                for(int j= 1; j<= x; ++j){
                        for(int i= 0; i<= n-(1<<j); ++i){
                                h[i][j]= h[i][j-1];
                                l[i][j]= l[i][j-1];
                                if(height[h[i][j]]< height[h[i+(1<<(j-1))][j-1]]){
                                        h[i][j]= h[i+(1<<(j-1))][j-1];
                                }
                                if(height[l[i][j]]>= height[l[i+(1<<(j-1))][j-1]]){
                                        l[i][j]= l[i+(1<<(j-1))][j-1];
                                }
                        }
                }
                int low= 1, high= n;
                int mid;
        //binary search   
                while(low< high){
                        mid= (low+high)>>1;
                        if(Ok(mid)){
                                low= mid+1;
                        }else{
                                high= mid-1;
                        }
                }
                while(!Ok(low))
                        --low;
                int a, b;
                int count= 0;
                for(int i= 0; i<= n-low; ++i){
                        a= getmax(i, i+low-1);
                        b= getmin(i, i+low-1);
                        if((height[a]-height[b])<= k){
                                rx[count]=i;
                                ry[count]=i+low-1;
                                ++count;
                        }
                }
                cout<<low<<' '<<count<<endl;
                for(int i= 0; i< count; ++i){
                        cout<<rx[i]+1<<' '<<ry[i]+1<<endl;
                }
        }
}

int exp2(unsigned x){
        int re= 0;
        while(x){
                x>>=1;
                ++re;
        }
        return  re-1;
}


int getmax(int x, int y){
        int p= exp2(y-x+1);
        if(height[h[x][p]]>= height[h[y-(1<<p)+1][p]]){
                return h[x][p];
        }else{
                return h[y-(1<<p)+1][p];
        }
}
int getmin(int x, int y){
        int p= exp2(y-x+1);
        if(height[l[x][p]]< height[l[y-(1<<p)+1][p]]){
                return l[x][p];
        }else{
                return l[y-(1<<p)+1][p];
        }
}

int Ok(int len){
        for(int i= 0; i<= n-len; ++i){
                if(height[getmax(i,i+len-1)]-height[getmin(i,i+len-1)]<= k){
                        return true;
                }
        }
        return false;
}