Cod sursa(job #1991662)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 17 iunie 2017 22:17:02
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
deque <int> dq;
int v[500001];
int main()
{
    int n,k,i;
    f>>n>>k;
    for(i=1;i<=n;i++)
        f>>v[i];
    dq.push_back(1);
    for(i=2;i<=k;i++)
    {
        while(!dq.empty() and v[i]<v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }
    int maxx=v[dq.front()];
    int in=1;
    int sf=k;
    for(i=k+1;i<=n;i++)
    {
        if(dq.front()<=i-k)
            dq.pop_front();
        while(!dq.empty() and v[i]<v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(v[dq.front()]>maxx)
        {
            maxx=v[dq.front()];
            sf=i;
            in=i-k+1;
        }
    }
    g<<in<<' '<<sf<<' '<<maxx;

    return 0;
}