Cod sursa(job #2387254)

Utilizator bluestorm57Vasile T bluestorm57 Data 24 martie 2019 14:26:04
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int v[500001],n,k;
int vf[500010];
char s[5000002];

void build(){
    int i,j=1,semn,r;
    int m=strlen(s);
    for(i=0; i<m; i++){
        semn=1;
        r=0;
        if(s[i]=='-'){
            semn=-1;
            i++;
        }

        while(s[i]>='0' && s[i]<='9'){
            r=r*10+s[i]-'0';
            i++;
        }

        v[j]=r*semn;
        j++;
    }
}

int main(){
    // ios::sync_with_stdio(0);
    //f.tie(0);
    //g.tie(0);
    int i,li,ls,poz,maxx;
    f>>n>>k;

    f.get();
    f.getline(s,5000002);
    //g<<s;return 0;
    build();

    //for(i=1; i<=n; i++)
    //    g<<v[i]<<" ";
    //return 0;

    li=1;
    ls=0;
    poz=k;
    maxx=-500010;

    for(i=1; i<=n; i++){
        while(li<=ls && v[i]<=v[vf[ls]])
            ls--;
        ls++;
        vf[ls]=i;

        if(vf[li]==i-k)
            li++;

        if(i>=k && v[vf[li]]>maxx){
            maxx=v[vf[li]];
            poz=i;
        }
    }

    g<<poz-k+1<<" "<<poz<<" "<<maxx;
    return 0;
}