Cod sursa(job #120093)

Utilizator alexeiIacob Radu alexei Data 4 ianuarie 2008 11:26:25
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
int n,k,a[500001],co[500001],min,minmax;
char sir[3600000];
int cauta(int p,int u,int x)
{
	int m;
	while(p<u){
		m=(p+u)/2;
		if(x<=a[co[m]])
			u=m;
		else
			p=m+1;
	}
	if(a[co[p]]<x)
		return p+1;
	return p;
}

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int min=30001,max,p=0,u=0,aa,bb;
	scanf("%d%d\n",&n,&k);
	int r,t=1;
    int i=1;
    char ok;
	int semn=1;
	gets(sir);
	for(char *pp=sir;*pp;++pp){
		if(*pp=='-')
		{
			++pp;
			a[i]=-(*pp-'0');
		}
		else
			if(*pp>='0'&&*pp<='9')
				a[i]=a[i]*10+(*pp-'0');
			else
				++i;
	}
	
    co[u++]=1;
	for(i=2; i<=k; i++){
        u=cauta(p,u-1,a[i]);
		co[u++]=i;
		if(a[co[p]]<min)
			min=a[co[p]];
	}
	max=min;
	aa=1;bb=k;
	for(i=k+1; i<=n; i++)
	{ 
      	if(co[p]+k<=i)
			++p;
		u=cauta(p,u-1,a[i]);
		co[u++]=i;
		min=a[co[p]];
		if(min>max){
			max=min;
			aa=i-k+1;
			bb=i;
		}
	} 
    printf("%d %d %d\n",aa,bb,max);
	return 0;
}