Cod sursa(job #333291)

Utilizator mlazariLazari Mihai mlazari Data 22 iulie 2009 10:25:18
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>

int n,k,bmax,pr=1,dp=0,du=0,v[500003],d[500003];

void add_deque(int id) {
  while((du>=dp)&&(v[d[du]]>=v[id])) du--;
  d[++du]=id;
}

int main() {
  int i,j=0,sign;
  char s[3500000];
  freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);
  scanf("%d %d\n",&n,&k);
  fgets(s,3500000,stdin);
  for(i=1;i<=n;i++) {
    if(s[j]!='-') sign=1;
    else { sign=-1; j++; }
    while((s[j]>='0')&&(s[j]<='9')) { v[i]=v[i]*10+s[j]-'0'; j++; }
    j++;
    v[i]*=sign;
  }
  for(i=1;i<=k;i++) add_deque(i);
  bmax=v[d[dp]];
  for(i=k+1;i<=n;i++) {
    if(d[dp]==i-k) dp++;
    add_deque(i);
    if(v[d[dp]]>bmax) {
      bmax=v[d[dp]];
      pr=i-k+1;
    }
  }
  printf("%d %d %d",pr,pr+k-1,bmax);
  return 0;
}