Cod sursa(job #597066)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 21 iunie 2011 02:00:47
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>

using namespace std;

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    int n,k,i,a[500001];
    f >> n >> k;
    for (i=1; i<=n; i++)
        f >> a[i];
    int minime[500001];
    int cap=1,coada=0;
    int min=-30000,poz;
    for (i=1; i<=n; i++)
    {
        while ((cap<=coada)&&(a[i]<=a[minime[coada]])) coada--;

        minime[++coada]=i;

        if (minime[cap] >=k)
        if (min<a[minime[cap]])
        {
            min=a[minime[cap]];
            poz=minime[cap];
        }

        if (minime[cap]==i-k+1) cap++;
    }
    int l=poz;
    while (a[l-1]>min) l--;
    g << l << ' ' << max(l+k-1,poz) << ' ' << min;
    return 0;
}