Cod sursa(job #2563811)

Utilizator Rares31100Popa Rares Rares31100 Data 1 martie 2020 14:52:03
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
#define Inf 30001

using namespace std;

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

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

int numar()
{
    static int poz=0;
    int semn=1;
    int nr=0;

    if(s[poz]=='-')
    {
        semn*=-1;
        poz++;
    }

    while(poz<s.size() && s[poz]!=' ')
    {
        nr=nr*10+s[poz]-'0';
        poz++;
    }

    poz++;

    return nr*semn;
}

int main()
{
    in>>n>>k;
    getline(in,s);
    getline(in,s);

    for(int i=1;i<=k-1;i++)
    {
        a[i]=numar();

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

        coada[++vf]=i;
    }

    for(int i=k;i<=n;i++)
    {
        a[i]=numar();

        if(coada[last]<=i-k)
            last++;

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

        coada[++vf]=i;

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

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

    return 0;
}