Cod sursa(job #326106)

Utilizator dacyanMujdar Dacian dacyan Data 23 iunie 2009 19:44:54
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#define INF 999999
using namespace std;

long n, k, i, st, dr, rez, poz, a[500000], q[500000];

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int main()
{
    fin >> n >> k;
    for  (i = 1; i <= n; i++)
        fin >> a[i];
    rez = INF;
    st = 1; dr = 1;
    for ( i = 1; i < k; i++)
    {
        while ( dr >= st && a[i] <= a[q[dr]] ) dr--;
        dr++;
        q[dr] = i;
    }    
    for ( i = k; i <= n; i++)
    {
        while (st <= dr && a[i] <= a[q[dr]] ) dr--;
        dr++;
        q[dr] = i;
        while ( st <= dr && q[st] < i - k + 1) st++;
        if ( a[q[st]] > rez)
        {
            rez = a[q[st]];
            poz = i;
        }
   }
   
   fout << poz - k + q << ' ' << poz << ' ' << rez << '\n';
   fin.close();
   fout.close();
   return 0;
}