Submission #674242

#	Time	Username	Problem	Language	Result	Execution time	Memory
674242		tibinyte	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	727 ms	152152 KiB

constellation3

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct bit
{
    vector<int> b;
    void resize(int n)
    {
        b = vector<int>(n + 2);
    }
    void update(int pos, int val)
    {
        int n = (int)b.size() - 1;
        for (int i = pos; i <= n; i += i & (-i))
        {
            b[i] += val;
        }
    }
    int query(int pos)
    {
        int ans = 0;
        for (int i = pos; i; i -= i & (-i))
        {
            ans += b[i];
        }
        return ans;
    }
    void update(int st, int dr, int val)
    {
        update(st, val);
        update(dr + 1, -val);
    }
};
struct rmq
{
    vector<vector<pair<int, int>>> rmq;
    vector<int> lg;
    void build(vector<int> a, int n)
    {
        lg = vector<int>(n + 1);
        for (int i = 2; i <= n; ++i)
        {
            lg[i] = lg[i / 2] + 1;
        }
        rmq = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>(lg[n] + 1));
        for (int i = 1; i <= n; ++i)
        {
            rmq[i][0] = {a[i], i};
        }
        for (int j = 1; j <= lg[n]; ++j)
        {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            {
                rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    pair<int, int> query(int st, int dr)
    {
        int pow_2 = lg[dr - st + 1];
        return min(rmq[st][pow_2], rmq[dr - (1 << pow_2) + 1][pow_2]);
    }
};
struct cartesian
{
    vector<int> a;
    vector<vector<int>> g;
    vector<vector<pair<int, int>>> stars;
    vector<vector<int>> jump;
    vector<int> tin;
    vector<int> tout;
    vector<int> dp;
    int p = 0;
    int root = 0;
    int max_jump = 0;
    int n = 0;
    void build(vector<int> _a, int _n)
    {
        n = _n;
        a = _a;
        dp = tin = tout = vector<int>(n + 1);
        g = vector<vector<int>>(n + 1);
        rmq t;
        t.build(a, n);
        max_jump = t.lg[n];
        jump = vector<vector<int>>(n + 1, vector<int>(max_jump + 1));
        stars = vector<vector<pair<int, int>>>(n + 1);
        function<void(int, int, int)> construct = [&](int st, int dr, int parent)
        {
            pair<int, int> qui = t.query(st, dr);
            if (parent != 0)
            {
                g[parent].push_back(qui.second);
                g[qui.second].push_back(parent);
                jump[qui.second][0] = parent;
            }
            else
            {
                jump[qui.second][0] = qui.second;
                root = qui.second;
            }
            for (int i = 1; i <= max_jump; ++i)
            {
                jump[qui.second][i] = jump[jump[qui.second][i - 1]][i - 1];
            }
            tin[qui.second] = ++p;
            if (qui.second != st)
            {
                construct(st, qui.second - 1, qui.second);
            }
            if (qui.second != dr)
            {
                construct(qui.second + 1, dr, qui.second);
            }
            tout[qui.second] = ++p;
        };
        construct(1, n, 0);
    }
    void insert(int node, int h, int coef)
    {
        int qui = node;
        for (int i = max_jump; i >= 0; --i)
        {
            if (a[jump[node][i]] >= h)
            {
                node = jump[node][i];
            }
        }
        stars[node].push_back({qui, coef});
    }
    int solve()
    {
        bit tree;
        bit tree2;
        tree.resize(p);
        tree2.resize(p);
        function<void(int, int)> dfs = [&](int node, int parent)
        {
            for (auto i : g[node])
            {
                if (i != parent)
                {
                    dfs(i, node);
                }
            }
            int sum = 0;
            for (auto i : g[node])
            {
                if (i != parent)
                {
                    sum += dp[i];
                }
            }
            tree.update(tin[node], tout[node], sum);
            dp[node] = sum;
            for (auto chain : stars[node])
            {
                dp[node] = max(dp[node], chain.second + tree.query(tin[chain.first]) - tree2.query(tin[chain.first]));
            }
            tree2.update(tin[node], tout[node], dp[node]);
        };
        dfs(root, 0);
        return dp[root];
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] = n - a[i];
    }
    cartesian t;
    t.build(a, n);
    int m;
    cin >> m;
    int sum = 0;
    for (int i = 1; i <= m; ++i)
    {
        int qui, wh, coef;
        cin >> qui >> wh >> coef;
        wh = n - wh + 1;
        sum += coef;
        t.insert(qui, wh, coef);
    }
    cout << sum - t.solve();
}

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