Submission #931388

#	Time	Username	Problem	Language	Result	Execution time	Memory
931388		boris_mihov	Road Construction (JOI21_road_construction)	C++17	100 / 100	1527 ms	497216 KiB

road_construction

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
const int MAXLOG = 20;

int n, k;
struct PersistentSegmentTree
{
    struct Node
    {
        llong min;
        int minIdx;
        int left, right;

        Node()
        {
            min = INF;
            minIdx = left = right = 0;
        }

        void assign(const Node &left, const Node &right)
        {
            if (left.min < right.min)
            {
                min = left.min;
                minIdx = left.minIdx;
            } else
            {
                min = right.min;
                minIdx = right.minIdx;
            }
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            if (left.min < right.min)
            {
                return left;
            } else
            {
                return right;
            }
        }
    };
    
    Node tree[2 * MAXN * MAXLOG];
    int cnt;

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].minIdx = l;
            return;
        }

        int mid = (l + r) / 2;
        tree[node].left = ++cnt;
        tree[node].right = ++cnt;
        build(l, mid, tree[node].left);
        build(mid + 1, r, tree[node].right);
        tree[node].assign(tree[tree[node].left], tree[tree[node].right]);
    }

    void update(int l, int r, int newNode, int oldNode, int queryPos, llong queryVal)
    {
        tree[newNode] = tree[oldNode];
        if (l == r)
        {
            tree[newNode].min = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid)
        {
            tree[newNode].left = ++cnt;
            update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
        } else
        {
            tree[newNode].right = ++cnt;
            update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
        }

        tree[newNode].assign(tree[tree[newNode].left], tree[tree[newNode].right]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = query(l, mid, tree[node].left, queryL, queryR);
        if (mid + 1 <= queryR) res = res + query(mid + 1, r, tree[node].right, queryL, queryR);
        return res;
    }

    void build()
    {
        cnt = 1;
        build(1, n, 1);
    }

    int update(int oldNode, int pos, llong val)
    {
        int newNode = ++cnt;
        update(1, n, cnt, oldNode, pos, val);
        return newNode;
    }

    Node query(int node, int l, int r)
    {
        return query(1, n, node, l, r);
    }
};

struct Point
{
    llong x, y;
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

struct PQelement
{
    llong value;
    char type;
    int updIdx;
    int myIdx;

    friend bool operator < (const PQelement &a, const PQelement &b)
    {
        return a.value > b.value;
    }
};

Point p[MAXN];
int perm[MAXN];
int inPerm[MAXN];
PersistentSegmentTree treePlus;
PersistentSegmentTree treeMinus;
std::priority_queue <PQelement> pq;
int nodePlus[MAXN];
int nodeMinus[MAXN];

void solve()
{
    std::sort(p + 1, p + 1 + n);
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int a, int b)
    {
        return p[a].y < p[b].y;
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        inPerm[perm[i]] = i;
    }

    treePlus.build();
    treeMinus.build();
    nodePlus[n] = nodeMinus[n] = 1;
    for (int i = n - 1 ; i >= 1 ; --i)
    {
        nodePlus[i] = treePlus.update(nodePlus[i + 1], inPerm[i + 1], p[i + 1].x + p[i + 1].y);
        nodeMinus[i] = treeMinus.update(nodeMinus[i + 1], inPerm[i + 1], p[i + 1].x - p[i + 1].y);

        PersistentSegmentTree::Node plusRes = treePlus.query(nodePlus[i], inPerm[i], n);
        if (plusRes.min != INF)
        {
            plusRes.min += -p[i].x - p[i].y;
            pq.push({plusRes.min, '+', plusRes.minIdx, i});
        }

        PersistentSegmentTree::Node minusRes = treeMinus.query(nodeMinus[i], 1, inPerm[i]);
        if (minusRes.min != INF)
        {
            minusRes.min += -p[i].x + p[i].y;
            pq.push({minusRes.min, '-', minusRes.minIdx, i});
        }
    }

    for (int time = 0 ; time < k ; ++time)
    {
        assert(pq.size());
        auto [val, type, updIdx, idx] = pq.top();
        pq.pop();

        std::cout << val << '\n';
        if (type == '+')
        {
            nodePlus[idx] = treePlus.update(nodePlus[idx], updIdx, INF);
            PersistentSegmentTree::Node plusRes = treePlus.query(nodePlus[idx], inPerm[idx], n);
            if (plusRes.min != INF)
            {
                plusRes.min += -p[idx].x - p[idx].y;
                pq.push({plusRes.min, '+', plusRes.minIdx, idx});
            }
        } else
        {
            nodeMinus[idx] = treeMinus.update(nodeMinus[idx], updIdx, INF);
            PersistentSegmentTree::Node minusRes = treeMinus.query(nodeMinus[idx], 1, inPerm[idx]);
            if (minusRes.min != INF)
            {
                minusRes.min += -p[idx].x + p[idx].y;
                pq.push({minusRes.min, '-', minusRes.minIdx, idx});
            }
        }
    }
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].y;
    }
}

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

int main()
{
    fastIOI();
    input();
    solve();
    
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35