Cod sursa(job #1683892)

Utilizator andreiudilaUdila Andrei andreiudila Data 10 aprilie 2016 17:14:01
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <string>
using namespace std;


ifstream fin("secventa.in");
ofstream fout("secventa.out");


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

int numar()
{
    int i=0;
    int numar=0;
    int semn=0;

    while(s[idx]==32)
    {
        ++idx;
    }



        if(s[idx]=='-') semn=-1,++idx;
        else semn=1;

    while(s[idx]>='0' && s[idx]<='9')
    {


        numar=numar*10+s[idx]-'0';

        ++idx;
    }

    return numar*semn;




}

int main()
{

  fin>>n>>k;

  fin.get();

  getline(fin,s);

  for(i=1;i<=n;++i)
    {
        a[i]=numar();
    }


    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;
}