Cod sursa(job #245029)

Utilizator katakunaCazacu Alexandru katakuna Data 16 ianuarie 2009 16:06:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<string.h>
#define INF 1<<30
#define MAXN 500011

int semn,j,x,ok,N,max,pi,pf,v[MAXN],d[MAXN],n,k,i,p,u;
char c[MAXN*10];


int main(){

FILE *f=fopen("secventa.in","r");
fscanf(f,"%d %d\n",&n,&k);
fgets(c,MAXN*10 - 1 ,f);

N=strlen(c); semn=1; j=0;

   for(i=0;i<N;i++){
   x=0;ok=0;

     if(c[i] == '-') semn = -1;

     while(c[i]>='0' && c[i]<='9' && i<=N){
     x=x*10+(c[i]-48);
     ok=1;
     i++;
     }

     x=semn*x;
     if(ok) {j++,v[j]=x;semn=1;}

   }

fclose(f);

p=1; u=1;
d[1]=1;

max=-INF;

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

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

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

     u++;
     d[u]=i;

     
     if(i>=k){
        if(v[d[p]] > max){
        max=v[d[p]];
        pi=i-k+1;
        pf=i;
        }
     }
  }

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

return 0;
}