Cod sursa(job #1817487)

Utilizator geni950814Geni Geni geni950814 Data 27 noiembrie 2016 21:47:44
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

const int N_MAX = 505050;
int V[N_MAX];

int secventa(int N, int K, int& pos) {
  int base;
  deque<int> dq;

  for(int i = 0; i < N; i++) {
    if(!dq.empty() && dq.front() == (i - K)) {
        dq.pop_front();
    }

    while(!dq.empty() && V[dq.back()] >= V[i]) {
      dq.pop_back();
    }
    dq.push_back(i);

    if(i == K - 1 || (i >= K && base < V[dq.front()])) {
      base = V[dq.front()];
      pos = i;
    }
  }
  return base;
}

int main() {
  ifstream in("secventa.in");
  int N, K, pos;
  in >> N >> K;
  ofstream out("secventa.out");
  for (int i = 0; i < N; i++) {
    in >> V[i];
  }
  int sec = secventa(N, K, pos);
  out << pos - K + 2 << " " << pos + 1 << " " << sec;
  return 0;
}