Cod sursa(job #355055)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 10 octombrie 2009 08:53:42
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <iostream>
#include <fstream>

#define MAXN      500000

#define FISIN     "secventa.in"
#define FISOUT    "secventa.out"

FILE *fin, *fout;

int key[MAXN];
int value[MAXN];
int start, stop;
int n, k;

int main() {

  std::ifstream fin(FISIN);
  fout = fopen(FISOUT, "wt");

  fin >> n >> k;
  for (int i = 0; i < k; ++i)  {
    int a; fin >> a;

    while (stop > start && a < value[stop - 1]) --stop;
    value[stop] = a; key[stop] = i; ++stop;
  }

  int best_start = 0; int best_base = value[0];
  
  for (int i = k; i < n; ++i) {
    int a; fin >> a;

    while (stop > start && a < value[stop - 1]) --stop;
    value[stop] = a; key[stop] = i; ++stop;

    if (key[start] == i - k) ++start;

    if (value[start] > best_base) {
      best_base = value[start];
      best_start = i - k + 1;
    }
  }

  best_start++;
  fprintf(fout, "%d %d %d\n", best_start, best_start + k - 1, best_base);

  fclose(fout);
  return 0;
}