Cod sursa(job #74526)

Utilizator floringh06Florin Ghesu floringh06 Data 26 iulie 2007 00:25:12
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>

using namespace std;

#define MAX_N 500005
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define INF 0x3f3f3f3f

int A[MAX_N];
int Deq[MAX_N];
int li,lf,N,i,K;
int BEST = -INF;
int In, Out;

    void Deqin (int x)
    {
         Deq[++lf]=x;
         if (A[x]<A[Deq[li]]) {  Deq[li]=x; lf=li; }  
         while (A[Deq[lf]]<A[Deq[lf-1]] && lf>li) 
          { Deq[lf-1]=Deq[lf]; lf--; }
         while (x-Deq[li]>=K) ++li;
    }      
    
    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        li=1;
        scanf ("%d %d" , &N, &K);
        for (i=1; i<=N; ++i) scanf ("%d",A+i);
        
        for (i=1; i<=N; ++i)
         {
          Deqin(i);
          if (i==250000) break;
          if (A[Deq[li]]>BEST && i>K-1) 
           {
             BEST=A[Deq[li]];
             In=i-K+1;
             Out=i;
           }
         }   
        printf("%d %d %d\n",In, Out, BEST);   
        return 0;
    }