Submission #476558

#	Time	Username	Problem	Language	Result	Execution time	Memory
476558		Alexandruabcde	Arboras (RMI20_arboras)	C++14	100 / 100	357 ms	21044 KiB

arboras

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int NMAX = 1e5 + 5;
typedef long long LL;
typedef pair <LL, int> PLI;

int Root = 0;

vector <int> G[NMAX];
int N;

int Dad[NMAX];
LL Cost[NMAX];
int Level[NMAX];
int Size[NMAX];
int poz[NMAX];
int prec[NMAX];
int Euler[NMAX];
PLI arb[4*NMAX];
LL Lazy[4*NMAX];

void Propag (int Node, int a, int b) {
    if (Lazy[Node] == 0) return;
    if (a == b) return;

    arb[2*Node].first += Lazy[Node];
    arb[2*Node+1].first += Lazy[Node];
    Lazy[2*Node] += Lazy[Node];
    Lazy[2*Node+1] += Lazy[Node];
    Lazy[Node] = 0;
}

void Initialize (int Node, int a, int b, int pos, LL val) {
    if (a == b) {
        arb[Node] = {val, Euler[a]};
        return;
    }

    int mij = (a + b) / 2;

    if (pos <= mij) Initialize(2*Node, a, mij, pos, val);
    else Initialize(2*Node+1, mij+1, b, pos, val);

    arb[Node] = max(arb[2*Node], arb[2*Node+1]);
}

void Update (int Node, int a, int b, int ua, int ub, LL val) {
    if (ua <= a && b <= ub) {
        Lazy[Node] += val;
        arb[Node].first += val;
        return;
    }

    Propag(Node, a, b);

    int mij = (a + b) / 2;

    if (ua <= mij) Update(2*Node, a, mij, ua, ub, val);
    if (mij < ub) Update(2*Node+1, mij+1, b, ua, ub, val);

    arb[Node] = max(arb[2*Node], arb[2*Node+1]);
}

PLI Query (int Node, int a, int b, int qa, int qb) {
    Propag(Node, a, b);
    if (qa > qb) return {0, -1};
    if (qa <= a && b <= qb) return arb[Node];

    int mij = (a + b) / 2;
    PLI Left = {0, -1}, Right = {0, -1};

    if (qa <= mij) Left = Query(2*Node, a, mij, qa, qb);
    if (mij < qb) Right = Query(2*Node+1, mij+1, b, qa, qb);

    return max(Left, Right);
}

PLI Maximum (int Node) {
    return Query(1, 1, N, poz[Node], poz[Node] + Size[Node] - 1);
}

PLI SecondMaximum (int Node) {
    PLI M = Maximum(Node);
    if (G[Node].size() <= 1) return Query(1, 1, N, poz[Node], poz[Node]);

    int st = 0, dr = G[Node].size()-1;
    int ans = 0;
    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (poz[G[Node][mij]] <= poz[M.second]){
            ans = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    ans = G[Node][ans];

    return max(Query(1, 1, N, poz[Node], poz[ans]-1), Query(1, 1, N, poz[ans] + Size[ans], poz[Node] + Size[Node] - 1));
}

int aux = 0;
void Dfs (int Node) {
    Size[Node] = 1;
    Euler[++aux] = Node;
    poz[Node] = aux;
    for (auto it : G[Node]) {
        Cost[it] += Cost[Node];
        Level[it] = Level[Node] + 1;
        Dfs(it);
        Size[Node] += Size[it];
    }
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i < N; ++ i ) {
        cin >> Dad[i];
        G[Dad[i]].push_back(i);
    }

    for (int i = 1; i < N; ++ i )
        cin >> Cost[i];

    Dfs(Root);
}

LL Sum_Total;
LL Sum_Maxim;
LL Sum_Second;
void Precalculare () {
    for (int i = 0; i < N; ++ i )
        Initialize(1, 1, N, poz[i], Cost[i]);

    ///Max + Second - 2 * LCA
    for (int i = 0; i < N; ++ i )
        prec[i] = i;

    for (int i = 0; i < N; ++ i ) {
        PLI x = Maximum(i);
        PLI y = SecondMaximum(i);

        Sum_Maxim += x.first;
        Sum_Second += y.first;
        Sum_Total += Cost[i];

        if (Level[prec[x.second]] > Level[i]) prec[x.second] = i;
    }

    cout << (Sum_Maxim + Sum_Second - 2 * Sum_Total) % MOD << '\n';
}

void Solve () {
    int Q;
    cin >> Q;
    for (; Q; -- Q ) {
        int node;
        LL v;
        cin >> node >> v;

        Sum_Total += 1LL * Size[node] * v;
        Sum_Maxim += 1LL * Size[node] * v;
        Sum_Second += 1LL * Size[node] * v;
        PLI val = Query(1, 1, N, poz[node], poz[node] + Size[node] - 1);
        val.first += v;
        Sum_Maxim += (Level[node] - Level[prec[val.second]]) * v;
        int curr = prec[val.second];

        while (curr > 0) {
            PLI Best_Dad_Path = Maximum(Dad[curr]);
            if (Best_Dad_Path > val) {
                PLI Second_Dad_Path = SecondMaximum(Dad[curr]);

                if (Second_Dad_Path < val) Sum_Second += (val.first - Second_Dad_Path.first);
                break;
            }
            PLI Second_Dad_Path = SecondMaximum(Dad[curr]);

            Sum_Second += Best_Dad_Path.first - Second_Dad_Path.first;
            int urm = prec[Best_Dad_Path.second];
            Sum_Maxim += (Level[curr] - Level[urm]) * (val.first - Best_Dad_Path.first);

            int Node = Dad[curr];
            int st = 0, dr = G[Node].size()-1;
            int ans = -1;
            while (st <= dr) {
                int mij = (st + dr) / 2;

                if (poz[G[Node][mij]] <= poz[Best_Dad_Path.second]){
                    ans = mij;
                    st = mij + 1;
                }
                else dr = mij - 1;
            }
            ans = G[Node][ans];
            prec[Best_Dad_Path.second] = ans;

            prec[val.second] = urm;
            curr = urm;
        }

        cout << (Sum_Maxim + Sum_Second - 2 * Sum_Total) % MOD << '\n';
        Update(1, 1, N, poz[node], poz[node]+Size[node]-1, v);
    }
}

int main () {
    Read();
    Precalculare();
    Solve();

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45