Cod sursa(job #2161905)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 11 martie 2018 21:53:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <deque>
#include <climits>
#include <iostream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

deque <int> d;
int n,k,i,maxim=INT_MIN,poz,v[500001];
int main()
{
    f>>n>>k;

    for(i=1; i<=n; i++)
    {
        f>>v[i];

        if(i<=k)
        {
            while(d.size()>=1&&v[d.front()]>=v[i])
            {
                d.pop_front();
            }

            d.push_front(i);
            if(v[d.back()]>maxim){maxim=v[d.back()];poz=k;}
            }

        else
        {



            while(d.size()>=1&&d.back()<=i-k)d.pop_back();
            while(d.size()>=1&&v[d.front()]>=v[i])
            {
                d.pop_front();
            }
            d.push_front(i);

            if(v[d.back()]>maxim)
            {
                maxim=v[d.back()];
                poz=i;
            }


        }


    }



    g<<poz-k+1<<" "<<poz<<" "<<maxim;

    return 0;
}