Cod sursa(job #71891)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 12 iulie 2007 00:58:00
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#define v 100//500002

int a[v],w[v],b[v];
long k,n,q,e,max,inc,sf,li,lf,l;

void citire()
{
freopen("secventa.in","r",stdin);
scanf("%ld%ld", &n, &k);
for (int i=0; i<n; i++)
    scanf("%d", &a[i]);
fclose(stdin);
}

void rezolvare()
{
q=-1;
e=0;
for (int i=0; i<n; i++)
    {
    w[++q]=a[i];
    b[q]=i;
    if (b[q]-b[e]+1>k)
       ++e;
    while (w[q]<w[q-1] && q-1>=e)
	  {
	  w[q-1]=w[q];
	  --q;
	  }
    l=i-b[e]+1;
    li=b[e];
    lf=i;
    while (a[li-1]>=w[e] && li-1>=0) && l+1<=k)
	  {
	  l++;
	  li--;
	  }
    if (w[e]>max && lf-li+1>=k)
       {
       max=w[e];
       inc=li+1;
       sf=lf+1;
       }
       else if (w[e]==max && lf-li+1>=k && li+1<=inc)
	       {
	       max=w[e];
	       inc=li+1;
	       sf=lf+1;
	       }
    }
}

void scrie()
{
freopen("secventa.out","w",stdout);
printf("%ld %ld %ld\n",inc,sf,max);
fclose(stdout);     
}     

int main()
{
citire();    
rezolvare();
scrie();
return 0;
}