Cod sursa(job #789863)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 septembrie 2012 17:51:13
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<iostream>
#include<queue>
#include<fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n, k, i, a[500001], res, st, dr, pres;
deque<int>dq;
int main()
{
    fin >> n >> k;
    for ( i = 1; i <= n; i++ )
    {
        fin >> a[i];
    }
    for ( i = 1; i <= n; i++ )
    {
        while ( !dq.empty() && a[i] < a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if ( i >= k )
        {
            while ( !dq.empty() && dq.front() <= i-k )
            {
                dq.pop_front();
            }
            if ( res < a[dq.front()])
            {
                res = a[dq.front()];
                pres = dq.front();
            }
        }
    }
    k--;
    st = dr = pres;
    while ( k && a[st-1] >= res && st-1 > 0)
    {
        st--;
        k--;
    }
    while ( k && a[dr+1] >= res && dr+1 <= n )
    {
        dr++;
        k--;
    }
    fout << st << ' ' << dr << ' ' << res;
    fin.close();
    fout.close();
    return 0;
}