Cod sursa(job #193072)

Utilizator MirageRobert Sandu Mirage Data 2 iunie 2008 10:03:25
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define N 500100
#define min(a,b) a<b?a:b
int n,k;
int a[N],q[N],poz[N];
int max=-(1<<30),pi,pf;
char s[1<<22];
void parsare(){
	int i,j,x;
    scanf("%d%d\n",&n,&k);
    fgets(s,1<<22, stdin);
    for(j=0,i=1;i<=n;++j,++i){
        if(s[j]=='-'){
            for(x=0,j++;s[j]>='0'&&s[j]<='9';++j)
                x=x*10+(s[j]-48);
            a[i]=x*(-1);
        }
        else{
            for(x=0;s[j]>='0'&&s[j]<='9';++j)
                x=x*10+(s[j]-48);
            a[i]=x;
        }
    }
}
int main(void){
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	parsare();
	int i,inc=1,sf=1,baza;
	q[1]=a[1];
	poz[1]=1;
	for(i=2;i<k;++i){
		while(a[i]<=q[sf]&&sf>0)
			sf--;
		q[++sf]=a[i];
		poz[sf]=i;
	}
	for(i=k;i<=n;++i){
		while(i-poz[inc]>=k)
			++inc;
		baza=min(a[i],q[inc]);
		if(baza>max){
			max=baza;
			pi=i-k+1;
			pf=i;
		}
		while(a[i]<=q[sf]&&sf>0)
			--sf;
		q[++sf]=a[i];
		poz[sf]=i;
		if(inc>sf)
			inc=sf;
	}
	printf("%d %d %d\n",pi,pf,max);
    return 0;
}