Cod sursa(job #2496011)

Utilizator lucametehauDart Monkey lucametehau Data 20 noiembrie 2019 09:19:29
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <deque>

using namespace std;

const int DIM = (1 << 17);

int n, k;
int vf, mx, ansl, ansr;

int v[500005];
deque <int> dq;

char nxt() {
  static char buff[DIM];
  static int bp = DIM;
  if(bp == DIM) {
    fread(buff, 1, DIM, stdin);
    bp = 0;
  }
  return buff[bp++];
}

void read(int &x) {
  static char ch;
  x = 0;
  do {
    ch = nxt();
  } while(ch < '0' || '9' < ch);
  do {
    x = x * 10 + ch - '0';
    ch = nxt();
  } while('0' <= ch && ch <= '9');
}

int main() {
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);
  read(n), read(k);
  for(int i = 1; i < k; i++) {
    read(v[i]);
    while(!dq.empty() && v[i] < v[dq.back()])
      dq.pop_back();
    dq.push_back(i);
  }
  mx = -30005;
  for(int i = k; i <= n; i++) {
    read(v[i]);
    while(!dq.empty() && v[i] < v[dq.back()])
      dq.pop_back();
    dq.push_back(i);
    if(i - dq.front() == k)
      dq.pop_front();
    if(v[dq.front()] > mx) {
      mx = v[dq.front()];
      ansl = i - k + 1, ansr = i;
    }
  }
  printf("%d %d %d", ansl, ansr, mx);
  return 0;
}