Submission #198438

#	Time	Username	Problem	Language	Result	Execution time	Memory
198438		model_code	Airplanes (LMIO17_lektuvai)	C++17	100 / 100	197 ms	26408 KiB

lektuvai

#include      <algorithm>
#include      <cassert>
#include      <iostream>
#include      <cassert>
#include      <vector>
#define endl '\n'
using namespace std;

struct Virsune {
    int pirmine_pozicija;
    pair<int, int> atsakinga;
    vector<int> vaikai;
};
int N, S;
vector<Virsune> priklausomybiu_medis;
vector<int> segmentuotas_medis;

void rasti_atsakingumo_rezius(int virsune, int &atsakingumo_pradzia) {
    Virsune &v = priklausomybiu_medis[virsune];
    v.atsakinga.first = atsakingumo_pradzia;
    atsakingumo_pradzia += 1;

    for (int vaikas: v.vaikai) {
        rasti_atsakingumo_rezius(vaikas, atsakingumo_pradzia);
    }

    v.atsakinga.second = atsakingumo_pradzia - 1;

#ifndef EVAL
    cerr << "Virsune " << virsune << " su pozicija " << v.pirmine_pozicija
         << " atsakinga uz [" << v.atsakinga.first
         << "; " << v.atsakinga.second << "]" << endl;
#endif
}

void rasti_atsakingumo_rezius(int virsune) {
    int atsakingumo_pradzia = 1;
    rasti_atsakingumo_rezius(virsune, atsakingumo_pradzia);
}

int saugi_segmentuoto_medzio_reiksme(int pozicija) {
    return pozicija < S ? segmentuotas_medis[pozicija] : 0;
}

void keisti_segmentuotame_medyje(int pozicija, int nauja_reiksme) {
    int indeksas = (S + 1) / 2 + pozicija - 1;
    assert(segmentuotas_medis[indeksas] <= nauja_reiksme);
    segmentuotas_medis[indeksas] = nauja_reiksme;
    for (indeksas = indeksas / 2 /* pradedam nuo indekso tevinės viršūnės */;
         indeksas                /* kol tėvinė viršūnė egzistuoja */;
         indeksas = indeksas / 2 /* lipam į kitą tėvinę viršūnę */) {
        // Viršūnės reikšmė -- maksimumas tarp vaikinių viršūnių.
        segmentuotas_medis[indeksas] = max(
                saugi_segmentuoto_medzio_reiksme(indeksas * 2),
                saugi_segmentuoto_medzio_reiksme(indeksas * 2 + 1));
    }
}

int rasti_maksimuma_tarp(int virsune, int virsune_pradzia, int virsune_pabaiga,
                         int intervalo_pradzia, int intervalo_pabaiga) {
    // Višūnė pilnai atsakinga už intervalo dalį.
    if (intervalo_pradzia <= virsune_pradzia &&
        virsune_pabaiga <= intervalo_pabaiga) {
        return segmentuotas_medis[virsune];
    }

    // Viršūnė yra neatsakinga už intervalo reikšmes.
    if (intervalo_pabaiga <= virsune_pradzia ||
        virsune_pabaiga <= intervalo_pradzia) {
        return 0;
    }

    // Viršūnė atsakinga už dalį reikšmių.
    const int virsune_intervalo_ilgis = virsune_pabaiga - virsune_pradzia + 1;
    return max(
      // Kairiojo vaiko reikšmė.
      rasti_maksimuma_tarp(virsune * 2,
                           virsune_pradzia,
                           virsune_pradzia + virsune_intervalo_ilgis / 2,
                           intervalo_pradzia, intervalo_pabaiga),
      // Dešiniojo vaiko reikšmė.
      rasti_maksimuma_tarp(virsune * 2 + 1,
                           virsune_pradzia + virsune_intervalo_ilgis / 2,
                           virsune_pabaiga,
                           intervalo_pradzia, intervalo_pabaiga)
    );
}
int rasti_maksimuma_tarp(const pair<int, int> &intervalas) {
    return rasti_maksimuma_tarp(1, 1, S / 2 + 1,
                                intervalas.first, intervalas.second + 1);
}

void atspausdinti_segmentuota_medi() {
    for (int i : segmentuotas_medis) {
        cerr << " " << i;
    }
    cerr << endl;
}
void atspausdinti_pozicijas() {
    cerr << "{";
    for (int i = 1; i <= N; i += 1) {
        cerr << (i == 1 ? "" : ", ")
             << i << ": "
             << rasti_maksimuma_tarp(priklausomybiu_medis[i].atsakinga);
    }
    cerr << "}" << endl;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);

    cin >> N;

    priklausomybiu_medis.resize(N + 1);
    for (int i = 1; i <= N; i += 1) {
        cin >> priklausomybiu_medis[i].pirmine_pozicija;
    }

    for (int i = 1; i <= N - 1; i += 1) {
        int turi_buti_pries;
        cin >> turi_buti_pries;
        priklausomybiu_medis[turi_buti_pries].vaikai.push_back(i);
    }

    rasti_atsakingumo_rezius(N);

    for (S = 1; S < N; S *= 2);
    S = 2 * S;
    segmentuotas_medis.resize(S);

    for (int i = 1; i <= N; i += 1) {
        keisti_segmentuotame_medyje(
            priklausomybiu_medis[i].atsakinga.first,
            priklausomybiu_medis[i].pirmine_pozicija);
    }

#ifndef EVAL
    cerr << "Segmentuotame medyje po jo inicilizavimo:";
    atspausdinti_segmentuota_medi();
    cerr << "Pozicijos: ";
    atspausdinti_pozicijas();
#endif

    int uzklausos;
    cin >> uzklausos;
    while (uzklausos--) {
        string uzklausa;
        int lektuvas;
        cin >> uzklausa >> lektuvas;
        const int lektuvo_pozicija =
            rasti_maksimuma_tarp(priklausomybiu_medis[lektuvas].atsakinga);
        if (uzklausa == "I") {
            cout << lektuvo_pozicija  << endl;
        } else if (uzklausa == "P") {
            int pastumpti;
            cin >> pastumpti;
            keisti_segmentuotame_medyje(
                priklausomybiu_medis[lektuvas].atsakinga.first,
                lektuvo_pozicija + pastumpti);
#ifndef EVAL
            cerr << "Segmentuotame medyje po pakeitimo:";
            atspausdinti_segmentuota_medi();
            cerr << "Visos pozicijos po pakeitimo: ";
            atspausdinti_pozicijas();
#endif
        }
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 40 / 40
• Subtask 4: 49 / 49