oj.uz

Submission #198438

# Submission time Handle Problem Language Result Execution time Memory
198438 2020-01-26T03:32:16 Z model_code Airplanes (LMIO17_lektuvai) C++17
100 / 100
 197 ms 26408 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 93 ms 14792 KB Output is correct
13 Correct 145 ms 25980 KB Output is correct
14 Correct 162 ms 25976 KB Output is correct
15 Correct 197 ms 25976 KB Output is correct
16 Correct 194 ms 26232 KB Output is correct
17 Correct 146 ms 26232 KB Output is correct
18 Correct 151 ms 26408 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 93 ms 14792 KB Output is correct
25 Correct 145 ms 25980 KB Output is correct
26 Correct 162 ms 25976 KB Output is correct
27 Correct 197 ms 25976 KB Output is correct
28 Correct 194 ms 26232 KB Output is correct
29 Correct 146 ms 26232 KB Output is correct
30 Correct 151 ms 26408 KB Output is correct
31 Correct 105 ms 11000 KB Output is correct
32 Correct 128 ms 17144 KB Output is correct
33 Correct 165 ms 26104 KB Output is correct
34 Correct 144 ms 25848 KB Output is correct
35 Correct 139 ms 20728 KB Output is correct
36 Correct 180 ms 13468 KB Output is correct
37 Correct 194 ms 17144 KB Output is correct
38 Correct 106 ms 10796 KB Output is correct
39 Correct 141 ms 18808 KB Output is correct
40 Correct 135 ms 11488 KB Output is correct