Cod sursa(job #1728990)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 13 iulie 2016 23:19:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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]);

    m = 0;
    for(int i = 1; i <= n; i++)
    {
        while(m > 0)
        {
            if(v[i] <= v[ stv[m] ])
                m--;
            else
                break;
        }

        if(m == 0)
            st[i] = 1;
        else
            st[i] = stv[m] + 1;
        stv[++m] = i;
    }

    m = 0;
    for(int i = n; i >= 1; i--)
    {
        while(m > 0)
        {
            if(v[i] <= v[ stv[m] ])
                m--;
            else
                break;
        }

        if(m == 0)
            dr[i] = n;
        else
            dr[i] = stv[m] - 1;
        stv[++m] = i;
    }

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