Cod sursa(job #1683854)

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

int i,j,k,l,r,n,mini,start,end,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;
    end=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, end=i;



    }

    fout<<start<<" "<<end<<" "<<maxi;

    return 0;
}