Cod sursa(job #272314)

Utilizator igsifvevc avb igsi Data 6 martie 2009 20:07:43
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream.h>

#define xx 500001

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

int n,k,maxb,pi,pf,v[xx],deque[xx],li,ls;

int main()
{
    int i;
    
    fin>>n>>k;
    
    for(i=1;i<=n;i++)
      fin>>v[i];
    
    for(i=1,maxb=-31000,li=1,ls=0;i<=n;i++)
    {
       while(li<=ls && v[i]<=v[deque[ls]]) ls--;
       
       deque[++ls]=i;
       
       if(deque[li]==i-k) li++;
       
       if(i>=k)
         if(v[deque[li]]>maxb)
         {
           maxb=v[deque[li]];
           pi=i-k+1;
           pf=i;
         }
    }
    
    fout<<pi<<' '<<pf<<' '<<maxb<<'\n';
    fout.close();
    return 0;
}