oj.uz

Submission #398524

# Submission time Handle Problem Language Result Execution time Memory
398524 2021-05-04T13:16:53 Z model_code Arboras (RMI20_arboras) C++17
100 / 100
 4291 ms 35504 KB 
/**
* 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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3036 KB Output is correct
2 Correct 9 ms 2892 KB Output is correct
3 Correct 13 ms 2892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2153 ms 30664 KB Output is correct
2 Correct 662 ms 29428 KB Output is correct
3 Correct 622 ms 29620 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4200 ms 32208 KB Output is correct
2 Correct 1631 ms 34316 KB Output is correct
3 Correct 2568 ms 31396 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3036 KB Output is correct
2 Correct 9 ms 2892 KB Output is correct
3 Correct 13 ms 2892 KB Output is correct
4 Correct 2153 ms 30664 KB Output is correct
5 Correct 662 ms 29428 KB Output is correct
6 Correct 622 ms 29620 KB Output is correct
7 Correct 4200 ms 32208 KB Output is correct
8 Correct 1631 ms 34316 KB Output is correct
9 Correct 2568 ms 31396 KB Output is correct
10 Correct 4291 ms 33148 KB Output is correct
11 Correct 1812 ms 34468 KB Output is correct
12 Correct 2620 ms 31364 KB Output is correct
13 Correct 2873 ms 35112 KB Output is correct
14 Correct 3096 ms 35504 KB Output is correct