Cod sursa(job #597065)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 21 iunie 2011 01:55:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 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++;
    }
    g << poz << ' ' <<poz+k-1 << ' ' << min;
    return 0;
}