Cod sursa(job #96423)

Utilizator asoare13Andrei Soare asoare13 Data 1 noiembrie 2007 16:09:07
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
// DEQUE

#include <stdio.h>
#define MAX 500001
#define IN "secventa.in"
#define OUT "secventa.out"

int A[MAX], V[MAX];

void adaug( int i, int p, int &u) {
  while (A[i] <= A[V[u]] && u >= p) u--;
  u++;
  V[u] = i;
}

int main()
{
  int poz, max, n, k, p = 0, u = 0, i;
  freopen( IN, "r", stdin);
  freopen( OUT, "w", stdout);
  scanf( "%d %d", &n, &k);
  for (i = 0; i < n; i++) scanf("%d", &A[i]);
  V[0] = 0;
  for (i = 1; i < k; i++) adaug( i, p, u);
  max = A[V[p]];
  poz = 0;
  for ( i = k; i < n; i++) {
    adaug( i, p, u);
    while (V[p] < i-k+1) p++;
    if ( max < A[V[p]]) {
      max = A[V[p]];
      poz = i-k+1;
    }
  }
  printf ("%d %d %d", poz+1, poz+k, max);
  fclose(stdin);
  fclose(stdout);
}