Cod sursa(job #1493667)

Utilizator herbertoHerbert Mohanu herberto Data 29 septembrie 2015 19:24:51
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.62 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;
  fscanf(fin, "%d%d", &n, &k);
  for(i=0; i<n; i++)
    fscanf(fin, "%d", &v[i]);
  ans=0;
  st=0;
  dr=0;
  for(i=0; i<n; i++){
    if(i-dq[st]>=k)
      st++;
    while((dr>st)&&(v[dq[dr-1]]>=v[i]))
      dr--;

    dq[dr++]=i;
    if(i>=k-1 && v[dq[st]]>ans){
      ans=v[dq[st]];
      poz=i;
    }
  }
  poz--;
  fprintf(fout, "%d %d %d\n", poz, poz+k-1, ans);
  fclose(fin);
  fclose(fout);
  return 0;
}