oj.uz

Submission #402017

# Submission time Handle Problem Language Result Execution time Memory
402017 2021-05-11T07:48:40 Z rama_pang Arboras (RMI20_arboras) C++17
100 / 100
 1658 ms 24572 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 7 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 1658 ms 21240 KB Output is correct
2 Correct 307 ms 19904 KB Output is correct
3 Correct 412 ms 20136 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1447 ms 22384 KB Output is correct
2 Correct 670 ms 23192 KB Output is correct
3 Correct 463 ms 20724 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 1658 ms 21240 KB Output is correct
5 Correct 307 ms 19904 KB Output is correct
6 Correct 412 ms 20136 KB Output is correct
7 Correct 1447 ms 22384 KB Output is correct
8 Correct 670 ms 23192 KB Output is correct
9 Correct 463 ms 20724 KB Output is correct
10 Correct 1409 ms 22340 KB Output is correct
11 Correct 664 ms 23236 KB Output is correct
12 Correct 563 ms 20692 KB Output is correct
13 Correct 1102 ms 24236 KB Output is correct
14 Correct 1032 ms 24572 KB Output is correct