86282024-01-23 23:04:09kukkermanBináris fa magassága (50 pont)cpp17Accepted 50/5019ms4952 KiB
#include <iostream>
#include <vector>

using Muveletek = std::vector<std::pair<int, int>>;

void beolvas(std::istream &be, int &n, Muveletek &muveletek) {
    int m;
    be >> n >> m;

    muveletek.resize(m);
    for (auto &[p, h] : muveletek) {
        be >> p >> h;
    }
}

void feldolgoz(int n, const Muveletek &muveletek) {
    const auto pontok_szama = (1 << n) - 1;

    std::vector<int> magassag(pontok_szama);
    std::vector<int> szulo_el(pontok_szama, 1);

    magassag[0] = n - 1;
    for (int i = 1; i < pontok_szama; i++) {
        const auto szulo = (i - 1) >> 1;
        magassag[i] = magassag[szulo] - 1;
    }

    for (auto [p, uj_hossz] : muveletek) {
        int akt = p - 1;
        szulo_el[akt] = uj_hossz;
        while (akt > 0) {
            const auto szulo = (akt - 1) >> 1;
            const auto testver = (akt & 1) > 0 ? akt + 1 : akt - 1;
            const auto uj_szulo_mag = std::max(magassag[akt]     + szulo_el[akt],
                                               magassag[testver] + szulo_el[testver]);

            if (magassag[szulo] != uj_szulo_mag) {
                magassag[szulo] = uj_szulo_mag;
                akt = szulo;

            } else {
                akt = 0;
            }
        }

        std::cout << magassag[0] << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n;
    Muveletek muveletek;
    beolvas(std::cin, n, muveletek);

    feldolgoz(n, muveletek);

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1700 KiB
2Accepted0/018ms3752 KiB
3Accepted2/23ms1980 KiB
4Accepted2/23ms2100 KiB
5Accepted2/23ms2192 KiB
6Accepted2/23ms2188 KiB
7Accepted3/33ms2188 KiB
8Accepted3/33ms2324 KiB
9Accepted3/33ms2380 KiB
10Accepted3/33ms2516 KiB
11Accepted2/218ms4384 KiB
12Accepted2/219ms4588 KiB
13Accepted2/219ms4784 KiB
14Accepted2/219ms4916 KiB
15Accepted2/219ms4800 KiB
16Accepted2/217ms4808 KiB
17Accepted2/217ms4808 KiB
18Accepted2/218ms4948 KiB
19Accepted2/217ms4808 KiB
20Accepted3/318ms4816 KiB
21Accepted3/318ms4820 KiB
22Accepted3/318ms4824 KiB
23Accepted3/318ms4952 KiB