Cod sursa(job #1759068)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 18 septembrie 2016 14:34:18
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <cctype>
#include <deque>
using namespace std;
deque<pair <int, int> >d;
pair<int, int>aux;
char c;
int get_nr(){
  bool semn = 0;
  int nr = 0;
  c = getc(stdin);
  if (c == '-'){
    semn = 1;
    c = getc(stdin);
  }
  while (isdigit(c)){
    nr = nr * 10 + c - '0';
    c = getc(stdin);
  }
  if (semn)
    nr *= -1;
  return nr;
}
int main(){
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);
  int n, k, poz, max = 0;
  n = get_nr();
  k = get_nr();
  for (aux.second = 1; aux.second <= k; ++ aux.second){
    aux.first = get_nr();
    while (!d.empty() && d.back().first >= aux.first)
      d.pop_back();
    d.push_back(aux);
  }
  max = d.front().first;
  poz = 1;
  for (aux.second = k + 1; aux.second <= n; ++ aux.second){
    aux.first = get_nr();
    while (!d.empty() && d.back().first >= aux.first)
      d.pop_back();
    d.push_back(aux);
    if (d.front().second == aux.second - k)
      d.pop_front();
    if (max < d.front().first){
      max = d.front().first;
      poz = aux.second - k + 1;
    }
  }
  printf("%d %d %d\n", poz, poz + k - 1, max);
  return 0;
}