Cod sursa(job #1361867)

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

#define DIM 10000
char buff[DIM];
int poz=0;
FILE *fin,*fout;

void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,fin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,fin),poz=0;
    }
}

int main()
{
    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);
    fread(buff,1,DIM,fin);
    citeste(n);
    citeste(k);

    for(int i=1;i<=k;i++)
    {
        citeste(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=1;
    e=k;

    for(int i=k+1;i<=n;i++)
    {
        citeste(t);

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

        while(!deq.empty()&&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=i-k+1;
            e=i;
        }
    }
    if(m<deq.front())
    {
        m=deq.front();
        s=n-k+1;
        e=n;
    }
    fprintf(fout,"%d %d %d",s,e,m);
}