Cod sursa(job #789347)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 17 septembrie 2012 21:13:37
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <deque>

using namespace std;

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

struct ceva
{
    int val, poz;
    ceva()
    {
        val = 0;
        poz = 1;
    }
    ceva(int V, int P)
    {
        val = V;
        poz = P;
    }
};


int a[500001];

int main()
{
    int n,k,x;
    fin>>n>>k;
    ceva ans;
    deque<ceva> D;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int i=1;i<=k;i++)
    {
        while(!D.empty() && D.back().val>=a[i])
            D.pop_back();
        D.push_back(ceva(a[i],i));
    }
    ans = D.front();
    for(int i=1+k;i<=n;i++)
    {
        while(!D.empty() && D.back().val>=a[i])
            D.pop_back();
        while(!D.empty() && D.front().poz<=i-k)
            D.pop_front();
        D.push_back(ceva(a[i],i));
        if(ans.val < D.front().val)
            ans = D.front();
    }
    int dr,st;
    st = dr = ans.poz;
    while(a[st-1]>ans.val && k)
    {
        st--;
        k--;
    }
    while(a[dr+1]>ans.val && k && dr<=n)
    {
        dr++;
        k--;
    }
    fout<<st<<' '<<dr<<' '<<ans.val<<'\n';



    fin.close();
    fout.close();
    return 0;
}