Cod sursa(job #17561)

Utilizator alex_damianDamian Alexandru alex_damian Data 16 februarie 2007 11:24:48
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>

#define MAXN 500001
#define FIN "secventa.in"
#define FOUT "secventa.out"


long a[MAXN], n, m, i, j, q[MAXN], p, u, k, max, poz;


int main () {
	freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);
  scanf("%ld %ld",&n, &k);
  for (i=1; i<=n; i++) scanf("%ld", &a[i]);

  p = 1; u = 1; q[u] = a[1];
  for (i=2; i<=k; i++) {
    while (q[u] < a[i]) u--;
    u++;
    q[u] = a[i];
  }
	max = q[p]; poz = i;
  for (i=k+1; i<=n; i++) {
    while (q[u] < a[i]) u--;
    u++;
    q[u] = a[i];

    if (q[p] == a[i-k]) p++;
    if (max < q[p]) {
      max = q[p];
      poz = i;
    }
  }
  printf("%ld %ld %ld\n", poz-k+1, poz, max);
  return 0;
}