Cod sursa(job #1052823)

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

using namespace std;


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

  unsigned int n, k;

  string line;

  {
    getline(fin, line);
    istringstream ss(line);
    ss >> n >> k;
  }

  getline(fin, line);
  istringstream in(line);

  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;
}