Cod sursa(job #1572405)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 18 ianuarie 2016 21:52:23
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <deque>

using namespace std;

const int MAX = 500001;
const int BUFF_MAX = 1000000;
int N, K, poz = BUFF_MAX, V[MAX];
char buff[BUFF_MAX];
deque<int> dq;

inline void reread_buffer() {
  if (poz == BUFF_MAX) {
    fread(buff, 1, BUFF_MAX, stdin);
    poz = 0;
  }
}

int read_int() {
  int result = 0;
  int sign = 1;

  while (buff[poz] < '0' || buff[poz] > '9') {
    if (buff[poz] == '-') {
      sign = -1;
    }
    poz++;
    reread_buffer();
  }

  while (buff[poz] >= '0' && buff[poz] <= '9') {
    result = result * 10 + buff[poz++] - '0';
    reread_buffer();
  }
  return sign * result;
}

int main() {
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);
  reread_buffer();
  N = read_int();
  K = read_int();
  int min = -30001;
  int end = 0;
  for(int i = 1; i <= N ; i++) {
    V[i] = read_int();
    while(!(dq.empty()) && V[dq.back()] >= V[i]) {
      dq.pop_back();
    }
    dq.push_back(i);

    if(dq.front() <= i-K) {
      dq.pop_front();
    }

    if(i >= K && min < V[dq.front()]) {
      min = V[dq.front()];
      end = i;
    }
  }
  printf("%d %d %d\n", end - K + 1, end, min);
  return 0;
}