Cod sursa(job #2563796)

Utilizator Rares31100Popa Rares Rares31100 Data 1 martie 2020 14:35:50
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
#define Inf 10000000

using namespace std;

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

int n,k,a[500001];
int coada[500001],last=1,vf;
int stS,drS,maxS=-Inf;

void adauga(int poz)
{
    if(last<=vf && coada[last]<=poz-k)
        last++;

    while(last<=vf && a[ coada[vf] ]>=a[poz])
        vf--;

    coada[++vf]=poz;
}

int main()
{
    in>>n>>k;

    for(int i=1;i<=n;i++)
        in>>a[i];

    for(int i=1;i<=k-1;i++)
        adauga(i);

    for(int i=k;i<=n;i++)
    {
        adauga(i);
        if(a[ coada[last] ]>maxS)
        {
            maxS=a[ coada[last] ];
            stS=i-k+1;
            drS=i;
        }
    }

    out<<stS<<' '<<drS<<' '<<maxS;

    return 0;
}