Cod sursa(job #1830769)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 17 decembrie 2016 08:55:40
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include<fstream>
#include<deque>
using namespace std;
int v[500001],i,n,k,ls,ld,mx;
deque<int> d;
int main()
{
    ifstream f("secventa.in");f>>n>>k>>v[1];
    d.push_front(1);
    for(i=2;i<=k;++i)
    {
        f>>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;mx=v[d.back()];
    for(i=k+1;i<=n;++i)
    {
        if(d.back()+k-1<i)
            d.pop_back();
        f>>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+1;
            ld=i;
            mx=v[d.back()];
        }
    }
    ofstream g("secventa.out");
    g<<ls<<" "<<ld<<" "<<mx;
    return 0;
}