Cod sursa(job #800403)

Utilizator Athena99Anghel Anca Athena99 Data 21 octombrie 2012 15:53:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cassert>
#include <cstdlib>

const int d=500001;
int v[d],deq[d];
char *buffer;

void read(int &x){
    int ok;

    while ((*buffer<'0'||*buffer>'9')&&*buffer!='-'){
        ++buffer;
    }

    if (*buffer=='-'){
        ok=-1;
        ++buffer;
    }else{
        ok=1;
    }

    x=0;
    while (*buffer>='0'&&*buffer<='9'){
       x=x*10+ok*(*buffer-'0');
       ++buffer;
    }
}

int main()
{
    int n=0,k=0,d1=1,d2=1,i=0,b=-d,s=1,f=0,fs;

    assert(freopen("secventa.in","r",stdin));
    fseek(stdin, 0, SEEK_END);
    fs=ftell(stdin);
    rewind(stdin);
    buffer=(char*)malloc(fs);
    assert(fread(buffer, 1, fs, stdin));
    read(n);
    read(k);
    f=k;
    deq[1]=1;
    for (i=1; i<n+1; ++i)
        read(v[i]);
    fclose(stdin);

    for (i=2; i<k; i++)
    {
		while (v[deq[d1]]>=v[i] && d1>0)
			--d1;
		++d1;
		deq[d1]=i;
	}

	for(i=k; i<n+1; i++)
	{
		while (v[deq[d1]]>=v[i] && d1>=d2)
			--d1;
        ++d1;
		deq[d1]=i;
		if (v[deq[d2]]>b)
		{
			b=v[deq[d2]];
			s=i-k+1;
			f=i;
		}
		if (deq[d2]<i-k+2)
			d2++;
	}

    assert(freopen("secventa.out","w",stdout));
    printf("%d %d %d\n",s,f,b);
    fclose(stdout);

	return 0;
}