Cod sursa(job #65054)

Utilizator sealTudose Vlad seal Data 6 iunie 2007 20:44:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Nm 500000
char S[7*Nm];
int A[Nm],Dq[Nm],n,k,s,f,m;

void read()
{
    int i;

    freopen("secventa.in","r",stdin);
    scanf("%d%d\n",&n,&k);
    gets(S);
    A[0]=atoi(strtok(S," "));
    for(i=1;i<n;++i)
	A[i]=atoi(strtok(NULL," "));
}

void solve()
{
    int i,l=0,r=-1;

    for(i=0;i<k;++i)
    {
	while(l<=r && A[i]<A[Dq[r]])
	    --r;
	Dq[++r]=i;
    }

    s=1; f=k;
    m=A[Dq[0]];

    for(;i<n;++i)
    {
	if(Dq[l]==i-k)
	    ++l;
	while(l<=r && A[i]<A[Dq[r]])
	    --r;
	Dq[++r]=i;
	if(A[Dq[l]]>m)
	{
	    m=A[Dq[l]];
	    s=i-k+2; f=i+1;
	}
    }
}

void write()
{
    freopen("secventa.out","w",stdout);
    printf("%d %d %d\n",s,f,m);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}