Cod sursa(job #789360)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 17 septembrie 2012 21:46:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <deque>
#include <cctype>

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;
    }
};

ceva ans;
deque<ceva> D;
int a[500001];

int main()
{
    int n,k;
    fin>>n>>k;
    char c;
    fin.get();

    for(int i=1;i<=n;i++)
    {
        a[i]=1;
        do
        {
            fin.get(c);
        }while(!(isdigit(c) || c=='-'));
        if(c=='-')
            a[i]=-1;
        else a[i] = c-'0';
        fin.get(c);
        while(isdigit(c))
        {
            a[i]=a[i]*10+(c-'0');
            fin.get(c);
        }
    }

    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;
    k--;
    st = dr = ans.poz;
    while(st-1>0 && 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;
}