Submission #1185990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185990		gyg	Tree (IOI24_tree)	C++20	31 / 100	2098 ms	96976 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5;

int n;
arr<vec<int>, N> ch;
arr<int, N> wg;

int nm;
arr<int, N> st, fn;
void st_dfs(int u = 1) {
    st[u] = ++nm;
    for (int v : ch[u]) st_dfs(v);
    fn[u] = nm;
}

void init(vec<sig> _pr, vec<sig> _wg) {
    n = _pr.size();
    for (int u = 1; u <= n; u++)
        ch[_pr[u - 1] + 1].push_back(u);
    for (int u = 1; u <= n; u++)
        wg[u] = _wg[u - 1];

    st_dfs();

    // for (int u = 1; u <= n; u++)
    //     cout << u << ": " << st[u] << " " << fn[u] << '\n';
}

struct Sgt {
    struct Nd { int sm, lz; };
    arr<Nd, 4 * N> tr;
    void intl() {
        tr.fill({0, 0});
    }
    void prp(int u) {
        for (int v : {2 * u, 2 * u + 1})
            tr[v].sm += tr[u].lz, tr[v].lz += tr[u].lz;
        tr[u].lz = 0;
    }
    void upd(int l, int r, int x, int u = 1, int lw = 1, int hg = n) {
        if (l <= lw && hg <= r) {
            tr[u].sm += x, tr[u].lz += x;
            return;
        }
        prp(u);
        int md = (lw + hg) / 2;
        if (l <= md) upd(l, r, x, 2 * u, lw, md);
        if (r > md) upd(l, r, x, 2 * u + 1, md + 1, hg);
        tr[u].sm = tr[2 * u].sm + tr[2 * u + 1].sm;
    }
    int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
        if (l <= lw && hg <= r) return tr[u].sm;
        prp(u);
        int md = (lw + hg) / 2, ans = 0;
        if (l <= md) ans += qry(l, r, 2 * u, lw, md);
        if (r > md) ans += qry(l, r, 2 * u + 1, md + 1, hg);
        return ans;
    }
} vl, rmv;

arr<set<pii>, N> ord;
void mrg(set<pii> &x, set<pii> &y) {
    if (x.size() < y.size()) swap(x, y);
    for (pii z : y) x.insert(z);
}

void dfs(int l, int r, int u = 1) {
    if (ch[u].empty()) { vl.upd(st[u], st[u], +l); return; }
    
    ord[u] = {{wg[u], u}};
    for (int v : ch[u]) {
        dfs(l, r, v);
        mrg(ord[u], ord[v]);
    }

    while (vl.qry(st[u], fn[u]) > r) {
        int v = ord[u].begin()->sec; ord[u].erase(ord[u].begin());
        if (rmv.qry(st[v], st[v])) continue;

        int x = vl.qry(st[v], fn[v]) - l, y = vl.qry(st[u], fn[u]) - r; 
        if (x <= y) {
            vl.upd(st[v], st[v], -x);
            rmv.upd(st[v], fn[v], +1);
        } else {
            vl.upd(st[v], st[v], -y);
            ord[u].insert({wg[v], v});
        }
    }
}

int query(sig l, sig r) {
    vl.intl(), rmv.intl(), ord.fill({});

    dfs(l, r);

    int ans = 0;
    for (int u = 1; u <= n; u++)
        ans += wg[u] * abs(vl.qry(st[u], st[u]));
    return ans;
}

• 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