Cod sursa(job #2216938)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 28 iunie 2018 13:53:45
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int aint[1000003][3],n,i,a,m,op,b,k,ma,in,sf;
void update(int st,int dr,int pos,int nod) {
    if(st==dr) {
        aint[nod][1]=a;
        aint[nod][2]=pos;
        while((aint[nod][1]<aint[nod/2][1] or aint[nod/2][2]==0) && nod>1) {
            swap(aint[nod],aint[nod/2]);
            nod/=2;
        }
    } else {
        int mij=(st+dr)/2;
        if(pos<=mij) {
            update(st,mij,pos,nod*2);
        } else {
            update(mij+1,dr,pos,nod*2+1);
        }
    }
}
void sterge(int nod) {
    aint[nod][1]=0;
    aint[nod][2]=0;
    if(nod<2*n) {
        if(aint[2*nod][1]<aint[2*nod+1][1] && aint[2*nod][2]!=0) {
            aint[nod][1]=aint[2*nod][1];
            aint[nod][2]=aint[2*nod][2];
            sterge(2*nod);
        } else if(aint[2*nod+1][2]!=0){
            aint[nod][1]=aint[2*nod+1][1];
            aint[nod][2]=aint[2*nod+1][2];
            sterge(2*nod+1);
        }
    }
}
int main() {
    f>>n>>k;
    for(i=1; i<=k; i++) {
        f>>a;
        update(1,k,i,1);
    }
    ma=-30001;
    if(aint[1][1]>ma) {
        ma=aint[1][1];
        in=1;
        sf=k;
    }
    for(i=k+1; i<=n; i++) {
        f>>a;
        update(1,n,i,1);
        while(aint[1][2]<=i-k) {
            sterge(1);
        }
        if(aint[1][1]>ma) {
            ma=aint[1][1];
            in=i-k+1;
            sf=i;
        }
    }
    g<<in<<" "<<sf<<" "<<ma<<'\n';
    return 0;
}