Mai intai trebuie sa te autentifici.

Cod sursa(job #355040)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 10 octombrie 2009 07:08:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>

#define MAXN      500000

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

FILE *fin, *fout;

class strange_queue {
public:

  struct elem { 
    elem(int k = 0, int v = 0) : key(k), value(v) { }
    int key, value; 
  };
  
  void add(const elem& e) {
    while (stop > start && e.value < m_list[stop - 1].value) --stop;
    m_list[stop] = e; ++stop;
  }
  void del(int key) {
    if (m_list[start].key == key) ++start;
  }
  int min() { return m_list[start].value; }

private:
  elem m_list[MAXN];
  int start, stop;
};

strange_queue q;

int main() {
  fin = fopen(FISIN, "rt");
  fout = fopen(FISOUT, "wt");

  int n, k; fscanf(fin, "%d %d", &n, &k);
  for (int i = 0; i < k; ++i)  {
    int a;
    fscanf(fin, "%d", &a);
    q.add(strange_queue::elem(i, a));
  }
  int best_start = 0; int best_base = q.min();
  
  for (int i = k; i < n; ++i) {
    int a; fscanf(fin, "%d", &a);
    int start = i - k;
    q.del(start);
    q.add(strange_queue::elem(i, a));
    int m = q.min(); 
    if (m > best_base) {
      best_base = m;
      best_start = i - k + 1;
    }
  }

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

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