Cod sursa(job #188268)

Utilizator katakunaCazacu Alexandru katakuna Data 7 mai 2008 17:57:30
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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)-1;
i=0;

int y,x=0,ii=0,se=1;

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

   if(y=='-')
   se=-1;

   else{

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

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

   }
  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;
}