Cod sursa(job #593886)

Utilizator Smaug-Andrei C. Smaug- Data 5 iunie 2011 02:21:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
//#include <cstdio>
#include <fstream>
using namespace std;

#define MAXN 500010
#define INF 50000


int main(){

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

  ifstream in("secventa.in");
  ofstream out("secventa.out");

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

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

  for(i=1; i<=N; ++i)
    //scanf("%d", A+i);
    in >> 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=A[D[l]]; minr=i;
    }
  }

  // printf("%d %d %d", minr-K+1, minr, minv);
  out << minr-K+1 << " " <<  minr << " " << minv << "\n";
  return 0;

}