Cod sursa(job #1818602)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 29 noiembrie 2016 14:49:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <deque>
const int N=5000003;
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
deque <int> d;
int n,v[N],k,nr=0;
int st,dr,Max=-999999999;
char x[10*N];
int ext(int &poz)
{
    short semn=1;
    if(x[poz]=='-')
    {
        semn=-1;
        poz++;
    }
    int num=0;
    while(x[poz]>='0'&&x[poz]<='9')
    {
        num=num*10+(x[poz]-'0');
        poz++;
    }
    return num*semn;
}
void parsare()
{
    for(int i=0;x[i]!=0;i++)
    {
       if(x[i]!=' ')
       {
           v[++nr]=ext(i);
           //g<<v[nr]<<" ";
       }
    }
   // g<<"\n";
}
int main()
{
    f>>n>>k;f.get();
    f.getline(x,10*N);
    parsare();
    for(int i=1;i<=n;i++)
    {
        while(!d.empty()&&v[d.back()]>=v[i])
        {
            d.pop_back();
        }
        d.push_back(i);
        if(d.front()+k==i)
        {
            d.pop_front();
        }
        if(i>=k)
        {
            if(Max<v[d.front()])
            {
                Max=v[d.front()];
                st=i;
                dr=i-k+1;
            }
            //g<<Max<<" "<<v[d.front()]<<"\n";
        }
    }
    //g<<"\n";
    g<<dr<<" "<<st<<" "<<Max;
    f.close();
    g.close();
    return 0;
}