Cod sursa(job #1052786)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 11 decembrie 2013 19:57:27
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

using namespace std;


int main()
{
  ifstream in("secventa.in", ios::in);
  ofstream out("secventa.out", ios::out);

  unsigned int n, k;
  in >> n >> k;
  vector<pair<int, unsigned int>> S(n);
  unsigned int i = 0u;
  for (auto& s : S) { in >> s.first; s.second = i++; }

  auto op = greater<pair<int, unsigned int>>();

  make_heap(begin(S), begin(S) + k, op);
  auto end_heap = begin(S) + k;
  auto ans = make_pair(S.front().first, k);

  for (auto i = end_heap; i < end(S); ++i) {
    while (S.front().second +k <= i->second) pop_heap(begin(S), end_heap--, op);
    if (ans.first < S.front().first && i->first >= S.front().first) ans = make_pair(S.front().first, i->second+1);
    *end_heap++ = *i;
    push_heap(begin(S), end_heap, op);
  }

  out << ans.second+1-k << ' ' << ans.second << ' ' << ans.first << endl;

  out.close();
  return 0;
}