Cod sursa(job #1683857)

Utilizator andreiudilaUdila Andrei andreiudila Data 10 aprilie 2016 17:00:00
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");

int i,j,k,l,r,n,mini,start,sfarsit,maxi,posmaxi;
int a[500001],d[500001];

int main()
{

  fin>>n>>k;
  for(i=1;i<=n;++i)
    fin>>a[i];

    l=1; r=1;
    d[1]=1;

    for(i=2;i<=k;++i)
        {
         while(a[i]<a[d[r]] && r>=l) --r;
         ++r;
         d[r]=i;
        }



    mini=a[d[l]];
    start=1;
    sfarsit=k;
    maxi=mini;
    posmaxi=d[l];

    for(i=k+1;i<=n;++i)
    {
        while(a[i]<a[d[r]] && r>=l) --r;
        ++r;

        d[r]=i;

        if(d[l]<i-k+1)
        ++l;

        if(a[d[l]]>maxi) maxi=a[d[l]], posmaxi=d[l], start=i-k+1, sfarsit=i;



    }

    fout<<start<<" "<<sfarsit<<" "<<maxi;

    return 0;
}