Cod sursa(job #1761726)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 22 septembrie 2016 19:37:43
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>

#define NMAX 500000

int deque [ NMAX ] ;
int v [ NMAX ] ;
int sfarsit, inceput ;

FILE *fin, *fout ;

void push_back (int x ) {
  deque[sfarsit] = x ;
  sfarsit++;
}

void pop_front() {
  inceput++;
}

void pop_back () {
  sfarsit--;
}

int form_numar () {
  int r, semn ;
  char c ;

  r = 0 ;
  c = fgetc (fin ) ;

  if (c == '-' ) {
    semn = -1 ;
    c = fgetc (fin) ;
  }
  else {
    r = r * 10 + (c - '0' ) ;
    semn = 1 ;
    c = fgetc (fin) ;
  }
  while (c != ' ' && c != '\n' ) {
    r = r * 10 + (c - '0' ) ;
    c = fgetc (fin) ;
  }
  return r * semn ;
}

int main() {

  fin = fopen ("secventa.in", "r" ) ;
  fout = fopen ("secventa.out", "w" ) ;

  int n, i, j, k, max, p1 ;

  fscanf (fin, "%d%d\n", &n, &k ) ;

  for (i = 0 ; i < n ; i++ ) {
    v[i] = form_numar() ;
  }

  inceput = 0 ;
  sfarsit = 1 ;
  deque[0] = v[0] ;
  for (i = 1 ; i < k - 1 ; i++ ) {
    while (v[i] < deque[sfarsit-1] && sfarsit > inceput) {
      pop_back() ;
    }
    push_back (v[i]) ;
  }

  max = p1 = -99999999;

  while (i < n ) {
    while (v[i] < deque[sfarsit-1] && sfarsit > inceput ) {
      pop_back() ;
    }
    push_back(v[i]) ;

    if (deque[inceput] > max ) {
      max = deque[inceput] ;
      p1 = i + 2 - k ;
    }
    if (v[ i - k  + 1 ] == deque[inceput] ) {
      pop_front() ;
    }
    i++;
  }

  fprintf (fout, "%d %d %d", p1, p1+k-1, max ) ;

  fclose (fin) ;
  fclose (fout ) ;
  return 0;
}