Submission #1196492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196492		tibinyte	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	0 / 100	0 ms	528 KiB

worst_reporter2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

mt19937 rng(69);

int random(int st, int dr)
{
    uniform_int_distribution<int> dist(st, dr);
    return dist(rng);
}

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator*(Mint oth)
    {
        return 1ll * val * oth.val;
    }
    void operator+=(Mint oth)
    {
        val = (*this + oth).val;
    }
    void operator-=(Mint oth)
    {
        val = (*this - oth).val;
    }
    void operator*=(Mint oth)
    {
        val = (*this * oth).val;
    }
};

Mint powmod(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 1)
    {
        return powmod(a, b - 1) * a;
    }
    Mint p = powmod(a, b / 2);
    return p * p;
}

/*
                 .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

#define int long long

const int inf = 1e16;

struct treap
{
    int key, prior;
    int coef;
    int lazy;
    treap *l, *r;
    treap(int val = 0, int dp = 0) : key(val), prior(random(1, 1e9)), coef(dp), lazy(0), l(nullptr), r(nullptr) {}
};

void push(treap *&t)
{
    if (!t)
    {
        return;
    }
    t->coef += t->lazy;
    if (t->l)
    {
        t->l->lazy += t->lazy;
    }
    if (t->r)
    {
        t->r->lazy += t->lazy;
    }
    t->lazy = 0;
}

void split(treap *t, treap *&l, treap *&r, int val)
{
    push(t);
    if (!t)
    {
        l = r = nullptr;
        return;
    }
    if (t->key <= val)
    {
        split(t->r, t->r, r, val);
        l = t;
    }
    else
    {
        split(t->l, l, t->l, val);
        r = t;
    }
}

void merge(treap *&t, treap *l, treap *r)
{
    push(l), push(r);
    if (!l || !r)
    {
        t = l ? l : r;
        return;
    }
    if (l->prior > r->prior)
    {
        merge(l->r, l->r, r);
        t = l;
    }
    else
    {
        merge(r->l, l, r->l);
        t = r;
    }
}

void insert(treap *&t, int val, int dp)
{
    treap *a = nullptr, *b = nullptr;
    split(t, a, b, val);
    merge(t, a, new treap(val, dp));
    merge(t, t, b);
}

int query(treap *t, int val)
{
    treap *a = nullptr, *b = nullptr, *c = nullptr;
    split(t, a, b, val);

    split(a, a, c, val - 1);

    int ans = c->coef;

    merge(t, a, c);
    merge(t, t, b);

    return ans;
}

void update(treap *&t, int st, int dr, int val)
{
    treap *a = nullptr, *b = nullptr, *c = nullptr;
    split(t, a, b, st - 1);
    split(b, b, c, dr);
    if (b)
    {
        b->lazy += val;
    }
    merge(t, a, b);
    merge(t, t, c);
}

void print(treap *&t)
{
    if (!t)
    {
        return;
    }
    print(t->l);
    cout << t->key << ' ';
    print(t->r);
}

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> h(n + 1), c(n + 1);
    vector<vector<int>> g(n + 1);

    vector<int> norm(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int par;
        cin >> par;
        if (i != 1)
        {
            g[par].push_back(i);
        }
        cin >> h[i] >> c[i];
        norm.push_back(h[i]);
    }

    vector<set<int> *> vals(n + 1);
    vector<treap *> t(n + 1);

    function<void(int)> dfs = [&](int node)
    {
        int qui = 0;
        int sz = 0;
        for (auto i : g[node])
        {
            dfs(i);
            if (vals[i]->size() > sz)
            {
                qui = i;
                sz = vals[i]->size();
            }
        }

        if (qui == 0)
        {

            vals[node] = new set<int>;
            t[node] = nullptr;

            vals[node]->insert(h[node]);
            vals[node]->insert(inf);

            insert(t[node], h[node], 0);
            insert(t[node], inf, c[node]);
            return;
        }

        vals[node] = vals[qui];
        t[node] = t[qui];

        treap *myT = nullptr;
        set<int> myunique;

        myunique.insert(h[node]);
        insert(myT, h[node], 0);

        for (auto i : g[node])
        {
            if (i == qui)
                continue;

            for (auto val = vals[i]->begin(); val != vals[i]->end(); ++val)
            {
                if (vals[node]->find(*val) == vals[node]->end() && myunique.find(*val) == myunique.end())
                {
                    myunique.insert(*val);
                    insert(myT, *val, 0);
                }
            }
        }

        for (auto i : g[node])
        {
            if (i == qui)
                continue;

            int f = 0;
            for (auto val = vals[i]->begin(); val != vals[i]->end(); ++val)
            {
                update(myT, f + 1, *val, query(t[i], *val));
                f = *val;
            }
        }

        for (auto i : myunique)
        {
            int oth = *vals[node]->upper_bound(i);

            update(myT, i, i, query(t[node], oth));
        }

        for (auto i : myunique)
        {
            insert(t[node], i, query(myT, i));
            vals[node]->insert(i);
        }

        for (auto i : g[node])
        {
            if (i == qui)
                continue;

            int f = 0;
            for (auto val = vals[i]->begin(); val != vals[i]->end(); ++val)
            {
                update(t[node], f + 1, *val, query(t[i], *val));
                f = *val;
            }
        }

        update(t[node], 1, h[node] - 1, c[node]);
        update(t[node], h[node] + 1, inf, c[node]);
    };
    dfs(1);

    int ans = inf;

    for (auto val = vals[1]->begin(); val != vals[1]->end(); ++val)
    {
        ans = min(ans, query(t[1], *val));
    }

    cout << ans << '\n';
}
/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before

Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21