Cod sursa(job #188259)

Utilizator katakunaCazacu Alexandru katakuna Data 7 mai 2008 17:38:00
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#include<string.h>

struct asfs {int v,p;}d[500002];
int i,n,k,p,u,max,a,b;
int v[500005];
char s[1500000];

int main(){



FILE *f=fopen("secventa.in","r");
fscanf(f,"%d %d\n",&n,&k);
fgets(s,1500000,f);
int nn;
nn=strlen(s);
i=0;

int y,x=0,ii=0;

  while(ii<=nn){
  y=s[ii];

   if(y>='0'&&y<='9')
   x=x*10+y-'0';

   else{
   i++;
   v[i]=x;
   x=0;
   }

  ii++;
  }


 // for(i=1;i<=n;i++)
  //fscanf(f,"%d",&v[i]);

fclose(f);

p=u=1;
d[1].v=v[1];
d[1].p=1;
max=-32000;

  for(i=2;i<=n;i++){

    while(p<=u&&d[p].p<=i-k)
    p++;

    while(p<=u&&d[u].v>v[i])
    u--;

    u++;
    d[u].p=i;
    d[u].v=v[i];

    if(i>=k&&d[p].v>max){
    a=d[u].p-k+1;
    max=d[p].v;
    }

  }

  b=a+k-1;

  while(a>1 && v[a-1]>=max)
  a--;

FILE *g=fopen("secventa.out","w");
fprintf(g,"%d %d %d",a,b,max);
fclose(g);

return 0;
}