Cod sursă (job #785853)

#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("burlane.in");
ofstream fout("burlane.out");

const int Nmax = 100005;

struct etaj{
    int etaj_scurgere, legatura_bloc_urmator, pasi_pana_la_legatura;
};

int n, q;
etaj etaje[Nmax];
int marime_grup, nr_grupuri;

void citire_configuratie_initiala(){
    fin >> n >> q;

    for(int i = 1; i <= n; i++){
        fin >> etaje[i].etaj_scurgere;
    }
}

void update_grup(int numar_grup){
    int vecin;
    int inceput_grup = marime_grup * (numar_grup - 1) + 1;
    int sfarsit_grup = min(inceput_grup + marime_grup - 1, n);

    for(int i = inceput_grup; i <= sfarsit_grup; i++){
        vecin = etaje[i].etaj_scurgere;

        if(vecin < inceput_grup){
            etaje[i].legatura_bloc_urmator = vecin;
            etaje[i].pasi_pana_la_legatura = 1;
        }
        else{
            etaje[i].legatura_bloc_urmator = etaje[vecin].legatura_bloc_urmator;
            etaje[i].pasi_pana_la_legatura = etaje[vecin].pasi_pana_la_legatura + 1;
        }
    }
}

void precalculare_informatii_grupuri(){
    marime_grup = sqrt(n);
    nr_grupuri = (n - 1) / marime_grup + 1;

    for(int i = 1; i <= nr_grupuri; i++){
        update_grup(i);
    }
}

void rezolvare_tip_1(){
    int pozitie, nr_pasi;

    fin >> pozitie;

    nr_pasi = 0;
    while(pozitie > 0){
        nr_pasi += etaje[pozitie].pasi_pana_la_legatura;
        pozitie = etaje[pozitie].legatura_bloc_urmator;
    }

    fout << nr_pasi << '\n';
}

void rezolvare_tip_2(){
    int pozitie, poz_scurgere;

    fin >> pozitie >> poz_scurgere;

    etaje[pozitie].etaj_scurgere = poz_scurgere;
    update_grup((pozitie - 1) / marime_grup + 1);
}

void citire_si_rezolvare_queryuri(){
    int tip;

    for(int i = 1; i <= q; i++){
        fin >> tip;

        if(tip == 1){
            rezolvare_tip_1();
        }
        else{
            rezolvare_tip_2();
        }
    }
}

int main(){
    citire_configuratie_initiala();
    precalculare_informatii_grupuri();
    citire_si_rezolvare_queryuri();

    return 0;
}