Submission #990469

#	Time	Username	Problem	Language	Result	Execution time	Memory
990469		peterandvoi	Arboras (RMI20_arboras)	C++17	100 / 100	146 ms	20692 KiB

arboras

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = int64_t;

const int N = 1e5 + 5, MOD = 1e9 + 7;

int n, q;
int p[N], tin[N], tout[N], pos[N], head[N], h[N];
ll d[N];
vector<int> g[N];

using Node = pair<ll, int>;

ll lz[4 * N];
Node s[4 * N];

void bld(int id = 1, int l = 1, int r = n) {
    if (l == r) {
        s[id] = {d[pos[l]], pos[l]};
        return;
    }
    int md = (l + r) / 2;
    bld(id * 2, l, md);
    bld(id * 2 + 1, md + 1, r);
    s[id] = max(s[id * 2], s[id * 2 + 1]);
}

void app(int id, ll x) {
    s[id].first += x;
    lz[id] += x;
}

void psh(int id) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
}

void upd(int u, int v, ll x, int id = 1, int l = 1, int r = n) {
    if (u <= l && r <= v) {
        app(id, x);
        return;
    }
    if (lz[id]) {
        psh(id);
    }
    int md = (l + r) / 2;
    if (u <= md) {
        upd(u, v, x, id * 2, l, md);
    }
    if (md < v) {
        upd(u, v, x, id * 2 + 1, md + 1, r);
    }
    s[id] = max(s[id * 2], s[id * 2 + 1]);
}

Node get(int u, int v, int id = 1, int l = 1, int r = n) {
    if (u <= l && r <= v) {
        return s[id];
    }
    if (lz[id]) {
        psh(id);
    }
    int md = (l + r) / 2;
    if (u <= md && md < v) {
        return max(get(u, v, id * 2, l, md), get(u, v, id * 2 + 1, md + 1, r));
    }
    if (md < u) {
        return get(u, v, id * 2 + 1, md + 1, r);
    }
    return get(u, v, id * 2, l, md);
}

int getc(int u, int x) {
    if (u == x) {
        return u;
    }
    int l = 0, r = g[u].size() - 1, res = 0;
    while (l <= r) {
        int md = (l + r) / 2;
        if (tin[x] <= tout[g[u][md]]) {
            res = g[u][md];
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    return res;
}

ll getsec(int u, int s) {
    ll res = 0;
    if (tin[u] < tin[s]) {
        res = max(res, get(tin[u], tin[s] - 1).first);
    }
    if (tout[s] < tout[u]) {
        res = max(res, get(tout[s] + 1, tout[u]).first);
    }
    return res;
}

int order;

void dfs(int u = 1) {
    pos[tin[u] = ++order] = u;
    for (int v : g[u]) {
        d[v] += d[u];
        h[v] = h[u] + 1;
        dfs(v);
    }
    tout[u] = order;
}

void add(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> p[i];
        g[++p[i]].emplace_back(i);
    }
    for (int i = 2; i <= n; ++i) {
        cin >> d[i];
    }
    dfs();
    bld();
    int res = 0;
    iota(head + 1, head + n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        int j = get(tin[i], tout[i]).second;
        add(res, (d[j] - d[i]) % MOD);
        ll s = getsec(i, getc(i, j));
        if (s >= d[i]) {
            add(res, (s - d[i]) % MOD);
        }
        if (h[head[j]] > h[i]) {
            head[j] = i;
        }
    }
    cout << res << "\n";
    cin >> q;
    while (q--) {
        int v;
        ll a;
        cin >> v >> a;
        v++;
        int x = v, y = a;
        auto [best, id] = get(tin[v], tout[v]);
        best += a;
        while (v > 1) {
            int u = head[id];
            add(res, ll(h[v] - h[u]) * a % MOD);
            v = u;
            u = p[v];
            if (u) {
                auto [nbest, nid] = get(tin[u], tout[u]);
                assert(tin[head[nid]] <= tin[u] && tin[u] <= tout[head[nid]]);
                ll s = getc(u, nid);
                ll sec = getsec(u, s);
                if (best >= sec) {
                    add(res, (best - sec) % MOD);
                    if (make_pair(best, id) > make_pair(nbest, nid)) {
                        head[id] = head[nid];
                        head[nid] = s;
                        a = best - nbest;
                        v = u;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        upd(tin[x], tout[x], y);
        cout << res << "\n";
    }
}

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