Cod sursa(job #1562775)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 5 ianuarie 2016 14:32:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <stdlib.h>
#define INFINIT 30001
#include <ctype.h>

int v[500002], stack[60003], st[500001], first=0;
char s[3500002];

int getNr(){
  while(s[first]==' ' || s[first]=='\n')
    first++;
  int c=1;
  if(s[first]=='-')
    c=-1,first++;
  int nr=0;
  while(isdigit(s[first])!=0){
    nr=nr*10+(s[first]-'0')*c;
    first++;
  }
  return nr;
}

int main()
{
  int n, k, i, vf, max, x;
  FILE *fi=fopen("secventa.in", "r"), *fo=fopen("secventa.out", "w");
  fscanf(fi, "%d%d", &n, &k);
  fgetc(fi);
  fgets(s,3500001,fi);
  for(i=1;i<=n;i++)
    v[i]=getNr();
  //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;
  max=0;
  for(i=n;i>=1;i--){
    while(v[stack[vf]]>=v[i])
      vf--;
    vf++;
    stack[vf]=i;
    x=stack[vf-1]-i-1;
    if(st[i]+x+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;
}