Cod sursa(job #159504)

Utilizator FlorinC1996Florin C FlorinC1996 Data 14 martie 2008 10:41:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
 #include<stdio.h>   
FILE* f= fopen("secventa.in", "rt");   
FILE* g= fopen("secventa.out", "wt");   
long int deque[500010],primul=1,ultimul,N,K,maxim,PozInit,PozFin,poz[500010],cnt1,cnt2;   
char a[20],b[3500100];   
  
int main()   
{fgets(a,20,f);   
for(;a[cnt1]<='9' && a[cnt1]>='0';cnt1++)   
  N=N*10+a[cnt1]-'0';   
cnt1++;   
for(;a[cnt1]<='9' && a[cnt1]>='0';cnt1++)   
  K=K*10+a[cnt1]-'0';   
fgets(b,3500100,f);   
for(long int i=1;i<=K;i++)   
    {long int aux=0,gasit=0;   
    if(b[cnt2]=='-')   
      {gasit=1;cnt2++;}   
    for(;b[cnt2]<='9' && b[cnt2]>='0';cnt2++)   
      aux=aux*10+b[cnt2]-'0';   
    if(gasit)   
      aux*=-1;   
    while(aux<deque[ultimul] && ultimul > 0)   
       ultimul--;   
    deque[++ultimul] = aux;   
    poz[ultimul] = i;   
    cnt2++;}   
maxim=deque[primul];   
PozInit=poz[primul];PozFin=poz[ultimul];   
for(long int i=K+1;i<=N;i++)   
  {long int aux=0,gasit=0;   
    if(b[cnt2]=='-')   
      {gasit=1;cnt2++;}   
    for(;b[cnt2]<='9' && b[cnt2]>='0';cnt2++)   
      aux=aux*10+b[cnt2]-'0';   
    if(gasit)   
      aux*=-1;   
   if(poz[primul]<i-K+1)   
     primul++;   
    while(aux<deque[ultimul] && ultimul >= primul)   
      ultimul--;   
  deque[++ultimul] = aux;   
  poz[ultimul] = i;   
  cnt2++;   
  if(maxim<deque[primul])   
    {maxim=deque[primul];   
    PozFin=i;   
    }   
  }   
fprintf(g,"%ld %ld %ld",PozFin-K+1,PozFin,maxim);   
fclose(f);   
fclose(g);   
return 0;   
}