Cod sursa(job #1493717)

Utilizator herbertoHerbert Mohanu herberto Data 29 septembrie 2015 20:28:36
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#define MAXN 5000000

int v[MAXN], dq[MAXN];

int main(){
  FILE*fin=fopen("secventa.in", "r");
  FILE*fout=fopen("secventa.out", "w");
  int n, k, i, st, dr, ans, poz, semn, nr, ret, max;
  char c;
  fscanf(fin, "%d%d", &n, &k);
  fgetc(fin);
  c=fgetc(fin);
  i=0;
  nr=0;
  semn=1;
  while(c!='\n' && c!=EOF){
    if(c=='-')
      semn=-1;
    else{
      if(c>='0' && c<='9')
        nr=nr*10+c-'0';
      else{
        nr*=semn;
        v[i++]=nr;
        nr=0;
        semn=1;
      }
    }
    c=fgetc(fin);
  }
  v[i]=semn*nr;
  st=0;
  poz=0;
  for(i=0; i<k; i++){
    while(poz>st && v[dq[poz-1]]>=v[i])
      poz--;

    dq[poz++]=i;
  }
//  for(i=0; i<n; i++)
//    printf("%d ", v[i]);
  ret=0;
  max=dq[st];
  for(i=k;i<n;i++){
    if(dq[st]==i-k)
      st++;

    while(poz>st && v[dq[poz-1]]>=v[i])
      poz--;

    dq[poz]=i;
    poz++;
    if(v[dq[st]]>v[max]){
      max=dq[st];
      ret=i-k+1;
    }
  }
//  printf("%d", max);
  fprintf(fout, "%d %d %d\n", ret+1, ret+k, v[max]);
  return 0;
}