Cod sursa(job #1544398)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 6 decembrie 2015 13:08:16
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>

using namespace std;
int n,k,i,mini,j,b,m,v[500005],w[500005];
int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    f>>n>>k;
    for(i=1; i<=k; i++)
    {
        f>>v[i];
        while(v[w[m]]>=v[i]&&m)
            m--;
        m++;
        w[m]=i;
    }
    mini=w[1];
    j=k;
    b=1;
    for(i=k+1; i<=n; i++)
    {
        f>>v[i];
        if(w[b]+k==i) b++;
        while(v[w[m]]>=v[i]&&m>=b)
            m--;
        m++;
        w[m]=i;
        if(v[w[b]]>v[mini])
        {
            mini=w[b];
            j=i;
        }
    }
    g<<j-k+1<<" "<<j<<" "<<v[mini]<<'\n';
    f.close(); g.close();
}