Cod sursa(job #943101)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 24 aprilie 2013 12:01:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstring>
#include<cstdio>

using namespace std;

char pars[5000000];

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(){
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);

  int n, k;
  scanf("%d%d\n", &n, &k);

  gets(pars);
  int pos = 0, p = 0, state = 0, num = 0, mm = 1;
  while(pars[p] != '\0'){
    if(pars[p] != ' '){
      if(pars[p] == '-')
        mm = -1;
      else{
        state = 1;
        num = num * 10 + pars[p] - '0';
      }
    }
    else  if(state){
      a[++pos] = num * mm;
      num = 0;
      mm = 1;
      state = 0;
    }
    ++p;
  }

  if(state){
      a[++pos] = num * mm;
      num = 0;
      mm = 1;
      state = 0;
  }

  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;
    }
  }

  printf("%d %d %d", lef, rai, mx);

  return 0;
}