Cod sursa(job #845829)

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