Submission #930299

#	Time	Username	Problem	Language	Result	Execution time	Memory
930299		boris_mihov	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	8 ms	39516 KiB

worst_reporter2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n;
struct SegmentTree
{
    struct Node
    {
        llong max;
        llong lazyAdd;
        llong lazySet;

        Node()
        {
            max = 0;
            lazyAdd = 0;
            lazySet = -1;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.max = std::max(left.max, right.max);
            return res;
        }
    };

    Node tree[4*MAXN];
    void mergeLazys(Node &to, Node from)
    {
        if (from.lazySet != -1)
        {
            to.lazySet = from.lazySet;
            to.lazyAdd = 0;
            return;
        }

        if (to.lazySet != -1)
        {
            to.lazySet += from.lazyAdd;
        } else
        {
            to.lazyAdd += from.lazyAdd;
        }
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazyAdd == 0 && tree[node].lazySet == -1)
        {
            return;
        }

        assert(tree[node].lazyAdd == 0 || tree[node].lazySet == -1);
        if (tree[node].lazyAdd == 0)
        {
            tree[node].max = tree[node].lazySet;
        } else
        {
            tree[node].max += tree[node].lazyAdd;
        }

        if (l < r)
        {
            mergeLazys(tree[2*node], tree[node]);
            mergeLazys(tree[2*node + 1], tree[node]);
        }

        tree[node].lazyAdd = 0;
        tree[node].lazySet = -1;
    }

    // void resetUpdate(int l, int r, int node, int queryPos)
    // {
    //     push(node, l, r);
    //     if (queryPos < l || r < queryPos)
    //     {
    //         return;
    //     }

    //     if (l == r)
    //     {
    //         tree[node] = Node();
    //         return;
    //     }

    //     int mid = (l + r) / 2;
    //     resetUpdate(l, mid, 2*node, queryPos);
    //     resetUpdate(mid + 1, r, 2*node + 1, queryPos);
    //     tree[node] = tree[2*node] + tree[2*node + 1];
    // }

    // void addUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
    // {
    //     push(node, l, r);
    //     if (queryR < l || r < queryL)
    //     {
    //         return;
    //     }

    //     if (queryL <= l && r <= queryR)
    //     {
    //         tree[node].lazyAdd = queryVal;
    //         push(node, l, r);
    //         return;
    //     }

    //     int mid = (l + r) / 2;
    //     addUpdate(l, mid, 2*node, queryL, queryR, queryVal);
    //     addUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    //     tree[node] = tree[2*node] + tree[2*node + 1];
    // }

    void addUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazyAdd = queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        addUpdate(l, mid, 2*node, queryL, queryR, queryVal);
        addUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void setUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazySet = queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        setUpdate(l, mid, 2*node, queryL, queryR, queryVal);
        setUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    llong pointQuery(int l, int r, int node, int queryPos)
    {
        push(node, l, r);
        if (l == r)
        {
            return tree[node].max;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) return pointQuery(l, mid, 2*node, queryPos);
        else return pointQuery(mid + 1, r, 2*node + 1, queryPos);
    }

    int query(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL || tree[node].max <= queryVal)
        {
            return n + 1;
        }

        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        int res = query(l, mid, 2*node, queryL, queryR, queryVal);
        if (res != n + 1) return res;
        return query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    }

    // void resetUpdate(int pos)
    // {
    //     update(1, n, 1, pos);
    // }

    void reset()
    {
        setUpdate(1, n + 1, 1, 1, n + 1, 0);
    }

    void addUpdate(int l, int r, llong val)
    {
        addUpdate(1, n + 1, 1, l, r, val);
    }

    void setUpdate(int l, int r, llong val)
    {
        setUpdate(1, n + 1, 1, l, r, val);
    } 

    llong pointQuery(int pos)
    {
        return pointQuery(1, n + 1, 1, pos);
    }

    int query(int l, int r, llong val)
    {
        return query(1, n + 1, 1, l, r, val);
    }
};


int h[MAXN];
int c[MAXN];
int sz[MAXN];
int perm[MAXN];
SegmentTree tree;
std::vector <int> g[MAXN];
std::set <int> vals[MAXN];
std::vector <llong> dp[MAXN];

void buildDFS(int node)
{
    sz[node] = 1;
    for (const int &u : g[node])
    {
        buildDFS(u);
        sz[node] += sz[u];
    }

    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        if (sz[g[node][i]] > sz[g[node][0]])
        {
            std::swap(g[node][i], g[node][0]);
        }
    }
}

void solveDFS(int node)
{
    if (g[node].empty())
    {
        vals[node].insert(n + 1);
        vals[node].insert(h[node]);
        tree.addUpdate(h[node] + 1, n + 1, c[node]);

        // std::cout << "dp vals: " << node << ":\n";
        // for (const int &val : vals[node])
        // {
        //     std::cout << val << " = " << tree.pointQuery(val) << '\n';
        // }

        return;
    }

    llong res = 0;
    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        int u = g[node][i];
        solveDFS(u);
        dp[u].reserve(vals[u].size());
        for (const int &val : vals[u])
        {
            dp[u].push_back(tree.pointQuery(val));
        }

        auto it = vals[u].lower_bound(h[u]);
        res += tree.pointQuery(*it);
        tree.reset();
    }

    solveDFS(g[node][0]);
    vals[node] = std::move(vals[g[node][0]]);

    auto it = vals[node].lower_bound(h[node]);
    res += tree.pointQuery(*it);

    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        int u = g[node][i];
        for (const int &newVal : vals[u])
        {
            tree.setUpdate(newVal, newVal, tree.pointQuery(*vals[node].lower_bound(newVal)));
        }
    }

    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        int u = g[node][i];
        assert(vals[u].size());
        int first = *vals[u].begin();
        tree.addUpdate(1, first, dp[u][0]);
        
        auto it = std::next(vals[u].begin());
        for (int idx = 1 ; it != vals[u].end() ; ++idx, ++it)
        {
            tree.addUpdate(*std::prev(it) + 1, *it, dp[u][idx]);
        }

        for (const int &val : vals[u])
        {
            vals[node].insert(val);
        }
    }

    tree.addUpdate(1, n + 1, c[node]);
    int firstPos = tree.query(1, h[node], res);
    if (firstPos != n + 1)
    {
        assert(firstPos <= h[node]);
        tree.setUpdate(firstPos, h[node], res);
    }

    vals[node].insert(h[node]);
    // std::cout << "res is: " << res << '\n';
    // std::cout << "dp vals: " << node << ":\n";
    // for (const int &val : vals[node])
    // {
    //     std::cout << val << " = " << tree.pointQuery(val) << '\n';
    // }
}

void solve()
{
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return h[x] < h[y];
    });

    int cnt = 0;
    int last = 0;

    for (int i = 1 ; i <= n ; ++i)
    {
        cnt += (h[perm[i]] > last);
        last = h[perm[i]];
        h[perm[i]] = cnt;
    }

    buildDFS(1);
    solveDFS(1);
    std::cout << tree.pointQuery(1) << '\n';
}

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

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void buildDFS(int)':
worst_reporter2.cpp:250:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'void solveDFS(int)':
worst_reporter2.cpp:277:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  277 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:298:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  298 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:307:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  307 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~

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