Cod sursa(job #529821)

Utilizator micky000Antal Ioan micky000 Data 6 februarie 2011 09:52:59
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
using namespace std;
 
ifstream in ("secventa.in");
ofstream out("secventa.out");
 
const int N=500005;
 
int v[N],dq[N],n,k,st,dr;
 
void dreapta(int i)
{
    while(st<=dr && v[dq[dr]]>=v[i])
        --dr;
}
 
 
void stanga(int i)
{
    if(i-dq[st]==k)
        ++st;
}
 
int main()
{
    int i,poz1,poz2,max1;
    in>>n>>k;
    for(i=1;i<=n;i++)
        in>>v[i];
    st=1;
    dr=0;
     
    for(i=1;i<=k;i++)
   {
        dreapta(i);
        dq[++dr]=i;
    }
    max1=v[dq[st]];
    poz1=1;
    poz2=k;
    for(;i<=n;i++)
    {
        stanga(i);
        dreapta(i);
        dq[++dr]=i;
        if (v[dq[st]]>max1)
        {
            max1=v[dq[st]];
            poz1=i-k+1;
            poz2=i;
        }
 
    }
     
    out<<poz1<<" "<<poz2<<" "<<max1<<"\n";
    return 0;
}