Cod sursa(job #1052842)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 11 decembrie 2013 20:52:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <vector>
#include <utility>

using namespace std;


int main()
{
  ifstream in;
  char buffer[4 * 1024 * 1024];
  in.rdbuf()->pubsetbuf(buffer, 1024 * 1024);
  in.open("secventa.in", ios::in);
  in.sync();
  ofstream out("secventa.out", ios::out);


  unsigned int n, k;
  in >> n >> k;

  vector<pair<int, unsigned int>> dq(n);
  auto b = 0u, e =0u;
  for (auto i = 0u; i < k; ++i) {
    int v = 0;
    in >> v;
    while (e>b && v < dq[e-1].first) --e;
    dq[e++] = make_pair(v, i);
  }
  auto ans = make_pair(dq[b].first, k);

  for (auto i = k; i < n; ++i) {
    int v = 0;
    in >> v;
    if (dq[b].second + k <= i) ++b;
    while (e>b && v < dq[e-1].first) --e;
    dq[e++] = make_pair(v, i);
    if (ans.first < dq[b].first) ans = make_pair(dq[b].first, i+1);
  }

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

  out.close();
  return 0;
}