Cod sursa(job #2888066)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 aprilie 2022 17:18:10
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
//Ilie Dmitru
#include<fstream>
#include<cstdio>
typedef long long int ll;
const int NMAX=500005;
const ll MOD=194767;

std::ifstream f("secventa.in");
std::ofstream g("secventa.out");
int v[NMAX], dq[NMAX], start=0, end=-1;
char s[NMAX*7];

int main()
{
    int N, K, i, maxB=-30005, pos, j, x, sgn;
    f>>N>>K;
    f.get();
    f.getline(s, NMAX*7);
    sgn=(s[0]=='-');
    for(i=sgn, j=0;s[i];++i)
    {
        if(s[i]==' ')
        {
            if(sgn)
                x=-x;
            v[j++]=x;
            x=0;
            i+=(sgn=(s[i+1]=='-'));
        }
        else
            x=x*10+s[i]-'0';
    }
    if(sgn)
        x=-x;
    v[j]=x;
    for(i=0;i<K;++i)
    {
        while(end>start && v[dq[end]]>=v[i])
            --end;
        dq[++end]=i;
    }
    pos=K-1;
    for(;i<N;++i)
    {
        while(end>start && v[dq[end]]>=v[i]) --end;
        dq[++end]=i;
        if(v[dq[start+=(dq[start]==i-K)]]>maxB)
            maxB=v[dq[start]], pos=i;
    }
    g<<pos-K+2<<' '<<pos+1<<' '<<maxB;
    f.close();
    g.close();
    return 0;
}