Cod sursa(job #2208584)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 30 mai 2018 16:18:17
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
deque<int> v;
int lel=-30010,n,k,i,a[500010];
int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++)
        f>>a[i];
    for(i=1;i<=k;i++)
    {
        while(v.size()&&(a[v.back()]>=a[i]))
            v.pop_back();
        v.push_back(i);
    }
    lel=a[v.front()];
    for(i=k+1;i<=n;i++)
    {
        while(v.size()&&(a[v.back()]>=a[i]))
            v.pop_back();
        v.push_back(i);
        while((i-v.front())>=k)
            v.pop_front();
        lel=max(lel,a[v.front()]);
    }
    for(i=1;i<=n;i++)
    {
        while(v.size()&&(a[v.back()]>=a[i]))
            v.pop_back();
        v.push_back(i);
        while((i-v.front())>=k)
            v.pop_front();
        if((i>=k)&&(lel==a[v.front()]))
        {
            g<<i-k+1<<' '<<i<<' '<<lel<<'\n';
            return 0;
        }
    }
    return 0;
}