oj.uz

Submission #402018

# Submission time Handle Problem Language Result Execution time Memory
402018 2021-05-11T07:48:40 Z rama_pang Arboras (RMI20_arboras) C++17
100 / 100
 1647 ms 24600 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e18;
const lint MOD = 1e9 + 7;

class SegTree {
 public:
  int sz;
  vector<int> cnt;
  vector<lint> tree;
  vector<lint> lazy;

  SegTree(int sz) : sz(sz), cnt(2 * sz), tree(2 * sz), lazy(2 * sz) {
    Build(1, 0, sz - 1);
  }

  void Build(int n, int tl, int tr) {
    if (tl == tr) {
      cnt[n] = 1;
      tree[n] = 0;
      lazy[n] = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Build(n + 1, tl, md);
    Build(z, md + 1, tr);
    Pull(n, n + 1, z);
  }

  void Pull(int n, int lc, int rc) {
    cnt[n] = cnt[lc] + cnt[rc];
    tree[n] = tree[lc] + tree[rc];
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Apply(int n, lint x) {
    tree[n] += cnt[n] * x;
    lazy[n] += x;
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n]);
    Apply(rc, lazy[n]);
    lazy[n] = 0;
  }

  void Update(int n, int tl, int tr, int l, int r, lint x) {
    if (l > tr || tl > r || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, x);
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Push(n, n + 1, z);
    Update(n + 1, tl, md, l, r, x);
    Update(z, md + 1, tr, l, r, x);
    Pull(n, n + 1, z);
  }

  void Update(int l, int r, lint x) {
    Update(1, 0, sz - 1, l, r, x);
  }

  lint Query(int p) {
    int n = 1, tl = 0, tr = sz - 1;
    while (tl != tr) {
      int md = (tl + tr) / 2;
      int z = n + 2 * (md - tl + 1);
      Push(n, n + 1, z);
      if (p <= md) {
        n = n + 1;
        tr = md;
      } else {
        n = z;
        tl = md + 1;
      }
    }
    assert(tl == tr);
    return tree[n];
  }

  lint Query() {
    return tree[1];
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;

  vector<int> st(N);
  vector<int> ist(N);
  vector<int> siz(N);
  vector<int> par(N);
  vector<int> root(N);
  vector<int> depth(N);
  vector<vector<int>> adj(N);

  par[0] = -1;
  for (int i = 1; i < N; i++) {
    cin >> par[i];
    adj[par[i]].emplace_back(i);
  }

  const auto DfsInit = [&](const auto &self, int u) -> void {
    siz[u] = 1;
    for (auto &v : adj[u]) {
      depth[v] = depth[u] + 1;
      self(self, v);
      siz[u] += siz[v];
      if (siz[v] > siz[adj[u][0]]) {
        swap(v, adj[u][0]);
      }
    }
  };

  const auto DfsHld = [&](const auto &self, int u) -> void {
    static int timer = 0;
    st[u] = timer++;
    ist[st[u]] = u;
    for (auto v : adj[u]) {
      root[v] = v == adj[u][0] ? root[u] : v;
      self(self, v);
    }
  };

  DfsInit(DfsInit, 0);
  DfsHld(DfsHld, 0);

  // Complexity by Link-Cut Tree Heavy-Light analysis
  // Keep segment tree, with dp[v] on position v
  // Update link-cut style on HLD
  // Time: O((N + Q) log^2 N).

  set<int> chain;
  for (int i = 0; i < N; i++) {
    chain.emplace(st[i]);
  }

  const auto ModifyChain = [&](int u, int sgn) {
    if (sgn == -1) {
      chain.erase(chain.find(st[u]));
    } else if (sgn == +1) {
      chain.emplace(st[u]);
    }
  };

  SegTree dp_1(N);
  SegTree dp_2(N);
  vector<int> prefer(N, -1);
  vector<lint> weight(N);

  const auto Update = [&](int prv) -> void {
    while (prv != 0) {
      int u = par[prv];
      lint newdp = dp_1.Query(st[prv]) + weight[prv];
      if (newdp <= dp_2.Query(st[u])) {
        // do nothing
        return;
      } else if (dp_2.Query(st[u]) < newdp && newdp <= dp_1.Query(st[u])) {
        dp_2.Update(st[u], st[u], newdp - dp_2.Query(st[u]));
        return;
      } else if (dp_1.Query(st[u]) < newdp) {
        lint dp1 = dp_1.Query(st[u]);
        lint dp2 = dp_2.Query(st[u]);
        int head = ist[*prev(chain.upper_bound(st[u]))];
        assert(root[u] == root[head]);

        if (prefer[u] == prv) {
          dp_1.Update(st[head], st[u], newdp - dp1);
          prv = head;
          continue;
        }

        if (prefer[u] != -1) {
          // insert prefer[u] as head chain
          ModifyChain(prefer[u], +1);
        }
        prefer[u] = prv;
        if (root[u] == root[prv]) {
          // delete prv as head chain
          ModifyChain(prv, -1);
        }

        dp_2.Update(st[u], st[u], dp1 - dp2);
        dp_1.Update(st[head], st[u], newdp - dp1);

        prv = head;
        continue;
      }
    }
  };

  for (int i = 1; i < N; i++) {
    int w;
    cin >> w;
    weight[i] += w;
    Update(i);
  }

  cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';

  int Q;
  cin >> Q;
  while (Q--) {
    int u, w;
    cin >> u >> w;
    weight[u] += w;
    Update(u);
    cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1647 ms 21236 KB Output is correct
2 Correct 317 ms 19920 KB Output is correct
3 Correct 335 ms 20208 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 22408 KB Output is correct
2 Correct 617 ms 23336 KB Output is correct
3 Correct 453 ms 20752 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1647 ms 21236 KB Output is correct
5 Correct 317 ms 19920 KB Output is correct
6 Correct 335 ms 20208 KB Output is correct
7 Correct 1287 ms 22408 KB Output is correct
8 Correct 617 ms 23336 KB Output is correct
9 Correct 453 ms 20752 KB Output is correct
10 Correct 1437 ms 22312 KB Output is correct
11 Correct 674 ms 23224 KB Output is correct
12 Correct 570 ms 20696 KB Output is correct
13 Correct 1089 ms 24320 KB Output is correct
14 Correct 1025 ms 24600 KB Output is correct