Submission #398524

#	Time	Username	Problem	Language	Result	Execution time	Memory
398524		model_code	Arboras (RMI20_arboras)	C++17	100 / 100	4291 ms	35504 KiB

arboras

/**
* user:  karpovich-a44
* fname: Evgeny
* lname: Karpovich
* task:  Arboras
* score: 100.0
* date:  2020-12-04 11:45:19.651657
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll mod = 1e9 + 7;
int const maxn = 1e5 + 5, logg = 18;
int p[maxn];
ll d[maxn];
vector < int > g[maxn];
ll ans = 0;
int L[maxn], R[maxn], timer;
ll psh[(1 << 20)];
int dp[maxn][logg];
pair < ll, int > maxi[(1 << 19)];

void dfs(int v, int p) {
    dp[v][0] = p;
    for (int j = 1; j < logg; ++j) {
        if (dp[v][j - 1] != -1) {
            dp[v][j] = dp[dp[v][j - 1]][j - 1];
        }
        else dp[v][j] = -1;
    }
    L[v] = timer++;
    for (auto u : g[v]) {
        dfs(u, v);
    }
    R[v] = timer++;
}

inline void push(int i) {
    if (psh[i]) {
        psh[2 * i + 1] += psh[i];
        psh[2 * i + 2] += psh[i];
        maxi[i].first += psh[i];
        psh[i] = 0;
    }
}

void update(int i, int l, int r, int lq, int rq, ll f) {
    if (lq >= r || l >= rq) {
        push(i);
        return;
    }
    if (lq <= l && r <= rq) {
        psh[i] += f;
        push(i);
        return;
    }
    push(i);
    int m = (r + l) / 2;
    update(2 * i + 1, l, m, lq, rq, f);
    update(2 * i + 2, m, r, lq, rq, f);
    maxi[i] = max(maxi[2 * i + 1], maxi[2 * i + 2]);
}

void adds(int v, ll x) {
    update(0, 0, timer, L[v], R[v] + 1, x);
}

inline int get_la(int v, int x) {
    for (int j = 0; j < logg; ++j) {
        if ((x&(1 << j))) v = dp[v][j];
    }
    return v;
}

inline pair < ll, int > get_max(int i, int l, int r, int lq, int rq) {
    if (lq >= r || l >= rq) return {-1, -1};
    push(i);
    if (lq <= l && r <= rq) return maxi[i];
    int m = (r + l) / 2;
    return max(get_max(2 * i + 1, l, m, lq, rq), get_max(2 * i + 2, m, r, lq, rq));
}

inline ll imax(int v) {
    if ((int)g[v].size() == 0) return 0;
    pair < ll, int > sum = get_max(0, 0, timer, L[v], R[v] + 1);
    ll goal = get_max(0, 0, timer, L[v], L[v] + 1).first;
    if ((int)g[v].size() == 1) return sum.first - goal;
    int lef = -1, righ = (int)g[v].size();
    while (righ - lef > 1) {
        int mid = (righ + lef) / 2;
        if (L[g[v][mid]] <= sum.second) lef = mid;
        else righ = mid;
    }
    sum.first -= 2 * goal;
    righ = lef;
    ll addf = 0;
    if (righ != 0) {
        addf = max(addf, get_max(0, 0, timer, L[v], R[g[v][righ - 1]] + 1).first);
    }
    if (righ != (int)g[v].size() - 1) {
        addf = max(addf, get_max(0, 0, timer, L[g[v][righ + 1]], R[v] + 1).first);
    }
    return sum.first + addf;
}

inline ll bonus(int v, int u, ll x) {
    ll last = imax(p[v]);
    adds(u, x);
    ll noww = imax(p[v]);
    adds(u, -x);
    return noww - last;
}

inline void update(int v, ll add) {
    int V = v;
    while (v > 0) {
        ll val = bonus(v, V, add);
        if (val == 0) break;
        int cur = 0;
        for (int b = logg - 1; b >= 0; --b) {
            if (dp[v][b] <= 0) continue;
            if (bonus(dp[v][b], V, add) == val) {
                cur += (1 << b);
                v = dp[v][b];
            }
        }
        ans += val * (ll)(cur + 1);
        v = p[v];
    }
}

void build(int i, int l, int r) {
    maxi[i] = {0, l};
    if (r - l == 1) return;
    int m = (r + l) / 2;
    build(2 * i + 1, l, m);
    build(2 * i + 2, m, r);
}

main() {
#ifdef karpovich
    freopen("input.txt", "r", stdin);
#endif // karpovich
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, v, q;
    ll add;
    cin >> n;
    for (int i = 1; i < n; ++i) cin >> p[i];
    for (int i = 1; i < n; ++i) g[p[i]].push_back(i);
    for (int i = 1; i < n; ++i) cin >> d[i];
    dfs(0, -1);
    build(0, 0, timer);
    for (int i = 1; i < n; ++i) {
        adds(i, d[i]);
    }
    for (int i = 0; i < n; ++i) {
        ans += imax(i);
    }
    cout << ans % mod << '\n';
    cin >> q;
    while (q--) {
        cin >> v >> add;
        update(v, add);
        adds(v, add);
        d[v] += add;
        cout << ans % mod << '\n';
    }
    return 0;
}

Compilation message (stderr)

arboras.cpp:142:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  142 | main() {
      |      ^

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