Cod sursa(job #943098)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 24 aprilie 2013 11:52:17
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>

using namespace std;

int l, r, dq[500005], a[500005];

void push(int x){
  while(r - l >= 0){
    if(a[x] < a[dq[r]])
      --r;
    else
      break;
  }
  dq[++r] = x;
}

void next(int x){
  while(x > dq[l])
    ++l;
}

int mn(){
  return a[dq[l]];
}

int main(){
  ifstream in("secventa.in");
  ofstream out("secventa.out");

  int n, k;
  in >> n >> k;

  for(int i = 1; i <= n; ++i)
    in >> a[i];

  for(int i = 1; i <= k; ++i)
    push(i);

  int mx = mn(), lef = 1, rai = k;

  for(int i = k + 1; i <= n; ++i){
    next(i - k + 1);
    push(i);
    if(mn() > mx){
      mx = mn();
      rai = i;
      lef = i - k + 1;
    }
  }

  out << lef << " " << rai << " " << mx;

  return 0;
}