Cod sursa(job #332690)

Utilizator MarquiseMarquise Marquise Data 19 iulie 2009 12:54:43
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream.h>

#define NMAX 500001

int n, k, max, v[NMAX], q[NMAX], poz[NMAX];

int main()
{
    int i, fmax, in, sf, p;

    ifstream f("secventa.in");
    ofstream g("secventa.out");
    
    f >> n >> k;
    
    for ( i = 1; i <= n; i++)
        f >> v[i];

    in = sf = 1;
    q[1] = 1;
    max = -30000;

    for ( i = 2; i <= n; i++)
    {

        if ( i - q[in] >= k)
           in++;

        for (; in <= sf && v[i] < v[q[sf]]; sf--);
        
        q[++sf] = i;

        
        if ( i >= k && v[q[in]] > max)
        {
             max = v[q[in]];
             fmax = i; 
        }     
    }    

    for ( p = fmax - k ; p > 0 && v[p] > max; p--);
    g  << p + 1 << " " << fmax << " " << max;

    return 0;
}