Cod sursa(job #2044987)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 21 octombrie 2017 17:36:41
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#define nmax 500005
using namespace std;
fstream f1("secventa.in", ios::in);
fstream f2("secventa.out", ios::out);
int n, k, a[nmax], maxi=-30005, in, sf, prim, ultim, cand[nmax];
///afli max minimelor din secv de k el
int main()
{
    int i;
    f1>>n>>k;
    for(i=1; i<=n; i++) f1>>a[i];
    prim=1; ultim=0;

    for(i=1; i<=n; i++)
    {
        while((prim<=ultim)&&(a[cand[ultim]]>= a[i])) ultim--;
        ultim++;
        cand[ultim]=i;

        if((prim<=ultim)&&(cand[prim]== i-k)) prim++;
        if((prim<=ultim)&&(i>=k))
        {
            if(a[cand[prim]]> maxi) {maxi=a[cand[prim]]; in=i-k+1; sf=i;}///min=cand[prim] de pe secv [i-k+1,i]
        }
    }
    f2<<in<<' '<<sf<<' '<<maxi;
    return 0;
}