Cod sursa(job #1728993)

Utilizator RG1999one shot RG1999 Data 13 iulie 2016 23:21:20
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>

using namespace std;
int n,i,v[500005],k,stv[500005],st[500005],dr[500005],m,in,sf,max1;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    stv[1]=1;
    m=1;
    st[1]=1;
    max1=-999999;
    for(i=2;i<=n;i++)
    {
        if(v[i]>v[stv[m]])
        {
            m++;
            stv[m]=i;
            st[i]=i;
        }
        else
           {

            while(v[i]<=v[stv[m]]&&m>=1)
            m--;
            m++;
            st[i]=st[stv[m]];
            stv[m]=i;
           }
    }
    stv[1]=n;
    m=1;
    dr[n]=n;
    for(i=n-1;i>=1;i--)
    {
         if(v[i]>v[stv[m]])
        {
            m++;
            stv[m]=i;
            dr[i]=i;
        }
         else
        {
                if(v[stv[m]]>=v[i])
                {
                    while(v[stv[m]]>=v[i]&&m>=1)
                    m--;
                    m++;
                }
                  dr[i]=dr[stv[m]];
                  stv[m]=i;
        }
    }
    for(i=1;i<=n;i++)
      if(v[i]>max1&&dr[i]-st[i]+1>=k)
      {
          in=st[i];
          max1=v[i];
      }
       printf("%d %d %d",in,in+k-1,max1);
}