Cod sursa(job #74511)

Utilizator floringh06Florin Ghesu floringh06 Data 26 iulie 2007 00:18:48
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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)
    {
         int k;
         Deq[++lf]=x; k=lf;
         if (A[x]<A[Deq[li]])
          {
            Deq[li]=x;
            lf=li;
          }  
         while (A[Deq[k]]<A[Deq[k-1]] && k>li) 
          { Deq[k-1]=Deq[k]; k--; }
         lf=k;
         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 (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;
    }