Cod sursa(job #1491956)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 26 septembrie 2015 18:36:40
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <stdlib.h>
#define INFINIT 30001;

int v[500002], stack[60003], st[500001], dr[500001];

int main()
{
  int n, k, i, vf, max;
  FILE *fi=fopen("secventa.in", "r"), *fo=fopen("secventa.out", "w");
  fscanf(fi, "%d%d", &n, &k);
  for(i=1;i<=n;i++)
    fscanf(fi, "%d", &v[i]);
  //de la stanga la dreapta
  v[0]=-INFINIT;
  vf=0;
  for(i=1;i<=n;i++){
    while(v[stack[vf]]>=v[i])
      vf--;
    vf++;
    stack[vf]=i;
    st[i]=i-stack[vf-1]-1;
  }
  //de la dreapta la stanga
  v[n+1]=-INFINIT;
  vf=0;
  stack[0]=n+1;
  for(i=n;i>=1;i--){
    while(v[stack[vf]]>=v[i])
      vf--;
    vf++;
    stack[vf]=i;
    dr[i]=stack[vf-1]-i-1;
  }
  max=0;
  for(i=1;i<=n;i++)
    if(st[i]+dr[i]+1>=k)
      if(v[i]>v[max])
        max=i;
  fprintf(fo, "%d %d %d", max-st[max], max-st[max]+k-1, v[max]);
  fclose(fi);
  fclose(fo);
  return 0;
}