Cod sursa(job #2408998)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 18 aprilie 2019 16:26:47
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int dq[500004], st, dr, v[500004], n, k;

int main()
{
    fin>>n>>k;
    int st=1, dr=0;
    for(int i=1;i<=n;++i) fin>>v[i];
    for(int i=1;i<=k;++i)
    {
        while(v[dq[dr]]<=v[i]&&dr>=st) dr--;
        v[++dr]=i;
    }
    int p=dq[dr], maxi=v[dq[st]];
    for(int i=k+1;i<=n;++i)
    {
        while(v[dq[dr]]>=v[i]&&dr>=st) dr--;
        dq[++dr]=i;
        while(dq[dr]-dq[st]>=k) st++;
        if(v[dq[st]]>maxi)
        {
            p=dq[dr];
            maxi=v[dq[st]];
        }
    }
    fout<<p-k+1<<" "<<p<<" "<<maxi<<"\n";
    return 0;
}