Cod sursa(job #845823)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 31 decembrie 2012 16:39:04
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
int n,k,i,a[500010],bmin,start,end;
deque<int> dq;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    bmin=-(1<<30);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        for(;!dq.empty() && i-dq.front()>=k;) dq.pop_front();
        for(;!dq.empty() && a[dq.back()]>a[i];) dq.pop_back();
        dq.push_back(i);
        if(i>=k)
        {
            if(a[dq.front()]>bmin)
            {
                bmin=a[dq.front()];
                start=i-k+1;
                end=i;
            }
        }
        //for(int j=0;j<dq.size();j++) printf("%d |%d|; ",a[dq[j]],dq[j]); printf("\n");
    }
    printf("%d %d %d\n",start,end,bmin);
    return 0;
}