Cod sursa(job #1761267)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 21 septembrie 2016 23:35:20
Problema Secventa Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>

#define NMAX 500000

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

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

void pop_front() {
  inceput++;
}

void pop_back () {
  sfarsit--;
}

int main() {

  FILE *fin, *fout ;

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

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

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

  for (i = 0 ; i < n ; i++ ) {
    fscanf (fin, "%d", &v[i] ) ;
  }

  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] ) {
      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 ) ;
  return 0;
}