Cod sursa(job #2121704)

Utilizator GiihuoTihufiNeacsu Stefan GiihuoTihufi Data 4 februarie 2018 11:00:58
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <deque>
#include <vector>
#include <iostream>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

deque<long> Deque;
vector<long> V,Base;

void WriteDeque()
{
    deque<long> D2=Deque;
    while(!D2.empty())
    {
        cout<<V[D2.front()]<<" ";
        D2.pop_front();
    }
    cout<<endl;
}

int main()
{
    long N,K,A;
    long Max=-30001,posi=-1,posj=0;
    f>>N>>K;

    for(long i=0;i<N;i++)
    {
        f>>A;
        V.push_back(A);

        if(!Deque.empty() && Deque.front()<=i-K)
            Deque.pop_front();

        if (Deque.empty()) Deque.push_back(i);
                    else
                    {
                        if(V[Deque.back()]<A) Deque.push_back(i);
                        else
                        {
                            while(!Deque.empty() && V[Deque.back()]>=A) Deque.pop_back();
                            Deque.push_back(i);
                        }
                    }
        //cout<<i-K+2<<" "<<i+1<<":";WriteDeque();
        if(i>K-2 && !Deque.empty())
        {
            Base.push_back(V[Deque.front()]);
        }
    }
    Max=Base[0],posi=0;
    for(int i=0;i<Base.size();i++)
        if(Max<Base[i]) Max=Base[i],posi=i;
    g<<posi+1<<" "<<posi+K<<" "<<Max;
    return 0;
}