Cod sursa(job #2269057)

Utilizator ianiIani Biro iani Data 25 octombrie 2018 18:02:40
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

int a[500005];
deque<int> deq;

int main()
{
    ifstream fin ("secventa.in");
    ofstream fout ("secventa.out");
    int n,k,inceput=0,sfarsit=0,maxi=-1;
    fin>>n>>k;
    for (int i=0;i<n;i++)
    {
        fin>>a[i];
        if (deq.empty()||a[i]>=a[deq.back()])
        {
            deq.push_back(i);
        }
        else
        {
            while(!deq.empty()&&a[i]<a[deq.back()])
                deq.pop_back();
            deq.push_back(i);
        }
        if (i>=k-1)
        {
            if (!deq.empty()&&i-deq.front()>=k)
                deq.pop_front();
            if (a[deq.front()]>maxi)
            {
                inceput=deq.front()+1;
                sfarsit=inceput+k-1;
                maxi=a[deq.front()];
            }
        }
    }
    fout<<inceput<<' '<<sfarsit<<' '<<maxi;
    return 0;
}