Cod sursa(job #597446)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 22 iunie 2011 11:08:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

int n,k,i,a[500001];
int minime[1000];
int cap=1,coada=0;
int minim=-30000,poz;

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

        minime[++coada]=i;

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

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