Codeforces 6 E. Exposition

問題

n冊の本がある。それぞれの高さはh[i]である。
この本から、

• 連続するa冊で
• 最も高い本と最も低い本の差がk以下

であるように本を選びたい。
aの最大値、そのときの本の選び方の数b、
具体的な本の選び方b通りを出力せよ。

制約条件

n≦10^5
h[i],k≦10^6

方針

しゃくとりっぽく本を見ていく。
現在の区間の本の集合をsetに入れておくことで、
最大値と最小値の参照がO(log n),値の挿入と削除もO(log n)で出来る。

ソースコード

int n,k,h[100000];
int ans[100000],a,b;

void run()
{
	cin>>n>>k;
	rep(i,n)cin>>h[i];
	a=b=0;
	set<pi> s;
	s.insert(mp(h[0],0));
	for(int i=0,j=0;i<n;i++){
		while(j+1<n){
			if(!s.empty()){
				int mn=(*s.begin()).first, mx=(*(--s.end())).first;
				if(max(mx,h[j+1])-min(mn,h[j+1])>k)break;
			}
			s.insert(mp(h[j+1],j+1));
			j++;
		}
		if(j-i+1>a)a=j-i+1, b=0;
		if(j-i+1==a)ans[b++]=i;
		s.erase(mp(h[i],i));
	}
	cout<<a<<" "<<b<<endl;
	rep(i,b){
		cout<<ans[i]+1<<" "<<ans[i]+a<<endl;
	}
}