Submission #1211396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211396		trimkus	Tree (IOI24_tree)	C++20	31 / 100	489 ms	38108 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 60000;


struct LazySeg {
    int n;
    vector<ll> tree, lz;
    LazySeg(int n) {
      this->n = n;
      tree = vector<ll>(4 * n);
      lz = vector<ll>(4 * n);
    }
    void init() {
      tree = vector<ll>(4 * n);
      lz = vector<ll>(4 * n);
    }
    void push(int i) {
        tree[i * 2] += lz[i];
        tree[i * 2 + 1] += lz[i];
        lz[i * 2] += lz[i];
        lz[i * 2 + 1] += lz[i];
        lz[i] = 0;
    }
    void update(int i, int l, int r, int ql, int qr, ll delta) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
          tree[i] += delta;
          lz[i] += delta;
          return;
        }
        push(i);
        int m = (l + r) / 2;
        if (ql <= m) update(i * 2, l, m, ql, qr, delta);
        if (qr > m) update(i * 2 + 1, m + 1, r, ql, qr, delta);
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
    void update(int ql, int qr, ll delta) {
      update(1, 1, n, ql, qr, delta);
    }
    ll query(int i, int l, int r, int ql, int qr) {
      if (l > qr || r < ql) return 0;
      if (ql <= l && r <= qr) return tree[i];
      push(i);
      int m = (l + r) / 2;
      return query(i * 2, l, m, ql, qr) + query(i * 2 + 1, m + 1, r, ql, qr);
    }
    ll query(int ql, int qr) {
      return query(1, 1, n, ql, qr);
    }
} sums(2 * MAXN), del(2 * MAXN);




int N;
vector<int> W;
vector<int> adj[MAXN];
vector<int> P;
int tin[MAXN], tout[MAXN];


void init(vector<int> _P, vector<int> _W) {
    P = _P;
    P[0] = -1;

    W = _W;
    N = (int)P.size();
    for (int i = 1; i < N; i++) {
        adj[P[i]].push_back(i);
    }
    int t = 0;
    auto dfs = [&](auto& dfs, int v) -> void {
      tin[v] = ++t;
      for (auto& u : adj[v]) {
        dfs(dfs, u);
      }
      tout[v] = t;
    };
    dfs(dfs, 0);
}


long long query(int L, int R) {
    sums.init();
    del.init();
    cerr << "Query " << L << " " << R << "\n";
    ll res = 0;
    vector<set<pair<int, int>>> mn(N);
    auto dfs = [&](auto& dfs, int v) -> void {
        // cerr << "Now at v = " << v << "\n";
        if ((int)adj[v].size() == 0) {
            res += 1LL * L * W[v];
            sums.update(tin[v], tin[v], +L);
            // cerr << "v = " << v << ", tin = " << tin[v] << " , tout = " << tout[v] << "\n";
            // cerr << "Sum at v = " << v << " is = " << sums.query(tin[v], tout[v]) << "\n";
            return;
        }
        mn[v].insert({W[v], v});
        for (auto& u : adj[v]) {
            dfs(dfs, u);
            if (mn[u].size() > mn[v].size()) swap(mn[u], mn[v]);
            for (auto& val : mn[u]) mn[v].insert(val);
            mn[u].clear();
        }
        ll current_sum = sums.query(tin[v], tout[v]);
        // cerr << "v = " << v << ", tin = " << tin[v] << " , tout = " << tout[v] << "\n";
        // cerr << "Sum at v = " << v << " is = " << current_sum << "\n";
        assert(current_sum >= L);
        while (current_sum > R) {
            int u = (*begin(mn[v])).second;
            int deleted = del.query(tin[u], tin[u]);
            if (deleted > 0) {
                mn[v].erase(mn[v].begin());
                continue;
            }
            ll need = min(current_sum - R, sums.query(tin[u], tout[u]) - L);
            current_sum -= need;
            sums.update(tin[u], tin[u], -need);
            assert(need >= 0);
            res += need * W[u];
            if (sums.query(tin[u], tout[u]) == L) {
                mn[v].erase(begin(mn[v]));
                del.update(tin[u], tout[u], +1);
            }
        }
    };
    dfs(dfs, 0);
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19