Cod sursa(job #1361847)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 26 februarie 2015 00:14:30
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#include<deque>

int main()
{
    FILE *fin,*fout;
    fin=fopen("secventa.in","r");
    fout=fopen("secventa.out","w");

    std::deque<int> deq;
    std::deque<int> pos;

    int n,k,t,m=-30000,s,e;
    fscanf(fin,"%d %d",&n,&k);

    for(int i=1;i<=k;i++)
    {
        fscanf(fin,"%d",&t);

        while(!deq.empty()&&t<=deq.back())
        {
            deq.pop_back();
            pos.pop_back();
        }

        deq.push_back(t);
        pos.push_back(i);
    }

    m=deq.front();
    s=pos.front()-k+1;
    e=pos.front();

    for(int i=k+1;i<=n;i++)
    {
        fscanf(fin,"%d",&t);

        //fprintf(fout,"%d %d^\n",pos.front(),i-k);

        if(pos.front()<=i-k)
        {
            pos.pop_front();
            deq.pop_front();
        }

        //fprintf(fout,"%d %d&\n",m,deq.front());

        if(m<=deq.front())
        {
            m=deq.front();
            s=i-k+1;
            e=i;
        }

        //fprintf(fout,"%d %d\n",t,deq.back());

        while(!deq.empty()&&t<=deq.back())
        {
            //fprintf(fout,"%d %d *\n",t,deq.back());
            deq.pop_back();
            pos.pop_back();
        }

        deq.push_back(t);
        pos.push_back(i);
    }
    if(m<=deq.front())
    {
        m=deq.front();
        s=n-k+1;
        e=n;
    }
    fprintf(fout,"%d %d %d",s,e,m);
}