Cod sursa(job #2266639)

Utilizator HoratioHoratiu Duma Horatio Data 22 octombrie 2018 20:15:12
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <deque>

using namespace std;


struct nr
{
    int indice,val;
};

int n,k;
nr a[50001];
nr mx;
nr x;
int i1,i2;
int st=1,dr=1;


void citire()
{
    scanf("%d %d\n",&n,&k);
    mx.val=-300001;
}


void parcurgere()
{
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&x.val);
        x.indice=i;
        a[++dr]=x;
        while(a[dr].val<a[dr-1].val && st<dr)
            {
            a[dr-1]=a[dr];
            dr--;
            }
    }
    for(int i=k+1;i<=n;i++)
    {
        scanf("%d",&x.val);
        x.indice=i;
        a[++dr]=x;
        int l=a[dr].indice-a[st].indice;
        if(l>=k-1)
        {
            if(a[st].val>mx.val)
            {
            mx=a[st];
            i1=i;
            i2=i1-k+1;
            st++;
            }
        }
        while(a[dr].val<a[dr-1].val && st<dr)
            {
            a[dr-1]=a[dr];
            dr--;
            }


    }
}

int main()
{


    freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
    citire();
    parcurgere();

    printf("%d %d %d",i2,i1,mx.val);





    return 0;
}