Submission #1210697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210697		badge881	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	790 ms	138452 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree
{
    vector<pair<int, int>> tree;
    segtree() : tree(524288) {}
    void update(int k, int x)
    {
        k += 262144;
        tree[k] = {x, k - 262144};
        while (k /= 2)
        {
            tree[k] = max(tree[2 * k], tree[2 * k + 1]);
        }
    }
    int get(int l, int r)
    {
        l += 262144;
        r += 262144;
        pair<int, int> ans = {0, 0};
        while (l <= r)
        {
            if (l & 1)
                ans = max(ans, tree[l++]);
            if (r % 2 == 0)
                ans = max(ans, tree[r--]);
            l /= 2;
            r /= 2;
        }
        return ans.second;
    }
};

pair<int, int> adj[200001];
int tree[200001];
vector<pair<int, int>> chains[200001];
int arr[200001];
int stidx[200001];
int lift[18][200001];
int idx[200001];
int DP[200001];
segtree seg;
int c;

void place(int x, int y, int c)
{
    int node = idx[x];
    for (int bit = 17; bit >= 0; bit--)
    {
        if (tree[lift[bit][node]] < y)
            node = lift[bit][node];
    }
    chains[node].emplace_back(x, c);
}

void build(int x, int l, int r)
{
    int mid = seg.get(l, r);
    idx[mid] = x;
    tree[x] = arr[mid];
    stidx[x] = mid;
    if (mid != l)
    {
        adj[x].first = ++c;
        lift[0][c] = x;
        build(c, l, mid - 1);
    }
    if (mid != r)
    {
        adj[x].second = ++c;
        lift[0][c] = x;
        build(c, mid + 1, r);
    }
}

void merge(pair<int, map<int, int>> &a, pair<int, map<int, int>> &b)
{
    if (a.second.size() < b.second.size())
        swap(a, b);
    int offset = b.first - a.first;
    for (auto [x, y] : b.second)
    {
        a.second[x] = y + offset;
    }
}

pair<int, map<int, int>> calc(int x)
{
    pair<int, map<int, int>> curr = {0, {}};
    pair<int, map<int, int>> l = {0, {}}, r = {0, {}};
    if (adj[x].first)
        l = calc(adj[x].first);
    if (adj[x].second)
        r = calc(adj[x].second);
    l.first += DP[adj[x].second];
    r.first += DP[adj[x].first];
    merge(curr, l);
    merge(curr, r);
    DP[x] = DP[adj[x].first] + DP[adj[x].second];
    curr.second[stidx[x]] = DP[x] - curr.first;
    for (auto [a, b] : chains[x])
    {
        DP[x] = max(DP[x], curr.second[a] + curr.first + b);
    }
    return curr;
}

int32_t main()
{
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
        seg.update(i, arr[i]);
    }
    build(++c, 1, n);
    assert(c == n);
    for (int bit = 1; bit < 18; bit++)
        for (int i = 1; i <= n; i++)
            lift[bit][i] = lift[bit - 1][lift[bit - 1][i]];
    tree[0] = 1e15;
    int m;
    scanf("%lld", &m);
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        scanf("%lld%lld%lld", &x, &y, &c);
        place(x, y, c);
        sum += c;
    }
    calc(1);
    printf("%lld\n", sum - DP[1]);
}

Compilation message (stderr)

constellation3.cpp: In function 'int32_t main()':
constellation3.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
constellation3.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
constellation3.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%lld", &m);
      |     ~~~~~^~~~~~~~~~~~
constellation3.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%lld%lld%lld", &x, &y, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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