Cod sursa(job #2521197)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 10 ianuarie 2020 15:29:29
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#define MAXN 500005
using namespace std;

int n, k, v[MAXN], arbInt[1024], maxBaza = -40000, resi;
ifstream fin("secventa.in");
ofstream fout("secventa.out");

void init(int nod, int st, int dr) {
    if (st == dr)
        arbInt[nod] = st;
    else {
        init(2*nod, st, (st+dr)/2);
        init(2*nod+1, (st+dr)/2+1, dr);

        if(v[arbInt[2*nod]] <= v[arbInt[2*nod+1]])
            arbInt[nod] = arbInt[2*nod];
        else
            arbInt[nod] = arbInt[2*nod+1];
    }
}

int query(int nod, int st, int dr, int i, int j) {
    if(i > dr || j < st) return -40000;
    if(st >= i && j >= dr) return arbInt[nod];

    int a = query(2*nod, st, (st+dr)/2, i, j);
    int b = query(2*nod+1, (st+dr)/2+1, dr, i, j);

    if(a == -40000) return b;
    if(b == -40000) return a;

    if(v[a] <= v[b])
        return arbInt[nod] = a;
    return arbInt[nod] = b;
}


int main() {
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
        fin >> v[i];
    init(1, 1, n);
    for(int i = 1; i+k <= n+1; i++) {
        int baza = v[query(1, 1, n, i, i+k-1)];
        if(baza > maxBaza) {
            maxBaza = baza;
            resi = i;
        }
    }
    fout << resi << ' ' << resi+k-1 << ' ' << maxBaza;
}