Cod sursa(job #593884)

Utilizator Smaug-Andrei C. Smaug- Data 5 iunie 2011 02:13:35
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <cstdio>

#define MAXN 500010
#define INF 50000


int main(){

  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);

  int N, K, i, l, r, minv, minr;
  int D[MAXN], A[MAXN];

  scanf("%d%d", &N, &K);
  l=1; r=0; minv=-1*INF;

  for(i=1; i<=N; i++)
    scanf("%d", A+i);

  for(i=1; i<=N; i++){

    if(l<=r && i-K==D[l])
      l++;
    
    while(l<=r && A[i]<=A[D[r]])
      r--;
    
    D[++r]=i;

    if(i>=K && A[D[l]]>minv){
      minv=D[l]; minr=i;
    }
  }

  printf("%d %d %d", minr-K+1, minr, A[minv]);

  return 0;

}