Cod sursa(job #28575)

Utilizator k_ounu_eddyIacob Eduard k_ounu_eddy Data 8 martie 2007 01:17:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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;
}