Cod sursa(job #1728998)

Utilizator RG1999one shot RG1999 Data 13 iulie 2016 23:27:54
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>

using namespace std;
int n,i,v[500005],k,stv[500005],st[500005],dr[500005],m,in,sf,max1;
#define DIM 10000
char buff[DIM];
int poz=0;

void citeste(int &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    citeste(n);
    citeste(k);
        for(i=1;i<=n;i++)
        citeste(v[i]);
        max1=-999999;
        for(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(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];
          max1=v[i];
        }
        printf("%d %d %d",in,in+k-1,max1);
}