Cod sursa(job #3240893)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 22 august 2024 18:25:06
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <deque>
#define lmax 500009
using namespace std;
ifstream  fin("secventa.in");
ofstream fout("secventa.out");
int N,K,i,v[lmax],st,dr,r;
deque <int>d(lmax);
int main()
{
    fin>>N>>K;

    for(i=1; i<=N; i++)
    {
        fin>>v[i];
    }

    r=-2000000009;

    for(i=1; i<=N; i++)
    {
        while(!d.empty() && i-d.back()>=K)
        {
            d.pop_back();
        }

        while(!d.empty() && v[d.front()]>=v[i])
        {
            d.pop_front();
        }

        d.push_front(i);

        if(i>=K && v[d.back()]>r)
        {
            r=v[d.back()];
            st=i-K+1;
            dr=i;
        }
    }

    fout<< st << " " << dr << " " << r;

    return 0;
}