Cod sursa(job #1830775)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 17 decembrie 2016 09:16:05
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include<fstream>
#include<deque>
using namespace std;
int v[500001],i,n,k,ls,ld,mx,poz=0;
deque<int> d;
ifstream f("secventa.in");
char buff[5000010];
void citeste(int &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == 5000010)
               f.getline(buff,5000010),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == 5000010)
               f.getline(buff,5000010),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}
int main()
{
    //f>>n>>k>>v[1];
    citeste(n);
    citeste(k);
    citeste(v[1]);
    d.push_front(1);
    ++k;++n;
    for(i=2;i<k;++i)
    {
        citeste(v[i]);
        if(v[i]<v[d.back()])
        {
            d.clear();
            d.push_front(i);
        }
        else
        {
            while(v[d.front()]>v[i])
            {
                d.pop_front();
            }
            d.push_front(i);
        }
    }
    //ls=1;
    ld=k-1;mx=v[d.back()];
    for(i=k;i<n;++i)
    {
        if(d.back()+k-2<i)
            d.pop_back();
        citeste(v[i]);
        if(v[i]<v[d.back()])
        {
            d.clear();
            d.push_front(i);
        }
        else
        {
            while(v[d.front()]>v[i])
            {
                d.pop_front();
            }
            d.push_front(i);
        }
        if(v[d.back()]>mx)
        {
            //ls=i-k+2;
            ld=i;
            mx=v[d.back()];
        }
    }
    ofstream g("secventa.out");
    g<<ld-k+2<<" "<<ld<<" "<<mx;
    return 0;
}