Cod sursa(job #962888)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 15 iunie 2013 21:09:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstring>
#include <deque>
int n,k,a[500005],q[500005],st,dr,d1,d2,mx=-30005;
long long sol=0;
char c[5000005];
FILE *f,*g;
void Parse()
{ char c2;
   int i,nr=0,semn=1,pas=0,len;
   scanf("%d %d\n",&n,&k);
   gets(c); len=strlen(c);
   for(i=0;i<=len;i++)
   { if (c[i]>=48 && c[i]<=57) nr=nr*10+(c[i]-'0');
     else
     {  if (c[i]=='-') semn=-1;
       if (c2>='0' && c2<='9')
       {pas++; nr*=semn;
        a[pas]=nr;
        semn=1;
        } nr=0;
     }
    c2=c[i];
    }
}
int main()
{ int i;
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
  Parse();
    for(i=1;i<=n;i++)
  { while(st<=dr && a[i]<a[q[dr]]) dr--;
    dr++; q[dr]=i;
      while(q[st]<=i-k) st++;
      if (i>=k)
      { if (a[q[st]]>mx) {mx=a[q[st]]; d1=i; d2=d1-k+1;} }
  }
  printf("%d %d %d",d2,d1,mx);
  //printf("%d %d\n",n,k);
  //for(i=1;i<=n;i++) printf("%d ",a[i]);
  return 0;
}