Submission #1265145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265145		tvgk	Road Construction (JOI21_road_construction)	C++20	100 / 100	1399 ms	680632 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, int>
const long mxN = 25e4 + 7;
const ll inf = 1e10 + 7;

struct node
{
    ii lt = {inf, 0}, rt = {inf, 0};
    int child[2];
};
vector<node> tree(2);

ii a[mxN], arr[mxN], mn[mxN];
int n, vt[mxN], m, root[mxN];
priority_queue<ii, vector<ii>, greater<ii>> pq;

int nw(int j)
{
    tree.push_back(tree[j]);
    return tree.size() - 1;
}

ii Get(int id, int vt, int j, int l = 1, int r = n)
{
    if (!j)
        return {inf, 0};

    if (r <= vt)
        return {tree[j].lt.fi + a[id].se + a[id].fi, tree[j].lt.se};

    if (vt <= l)
        return {tree[j].rt.fi - a[id].se + a[id].fi, tree[j].rt.se};

    int mid = (l + r) / 2;
    return min(Get(id, vt, tree[j].child[0], l, mid), Get(id, vt, tree[j].child[1], mid + 1, r));
}

void Upd(int id, int vt, int j, int l = 1, int r = n)
{
    if (l == r)
    {
        if (id > 0)
        {
            tree[j].lt = {-a[id].fi - a[id].se, l};
            tree[j].rt = {a[id].se - a[id].fi, l};
        }
        else
            tree[j].lt = tree[j].rt = {inf, 0};

        return;
    }

    int mid = (l + r) / 2;
    if (vt <= mid)
    {
        tree[j].child[0] = nw(tree[j].child[0]);
        Upd(id, vt, tree[j].child[0], l, mid);
    }
    else
    {
        tree[j].child[1] = nw(tree[j].child[1]);
        Upd(id, vt, tree[j].child[1], mid + 1, r);
    }
    tree[j].lt = min(tree[tree[j].child[0]].lt, tree[tree[j].child[1]].lt);
    tree[j].rt = min(tree[tree[j].child[0]].rt, tree[tree[j].child[1]].rt);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
        arr[i] = {a[i].se, i};
    sort(arr + 1, arr + n + 1);

    for (int i = 1; i <= n; i++)
        vt[arr[i].se] = i;

    root[1] = 1;
    for (int i = 1; i <= n; i++)
    {   
        mn[i] = Get(i, vt[i], root[i]);
        pq.push({mn[i].fi, i});

        root[i + 1] = nw(root[i]);
        Upd(i, vt[i], root[i + 1]);
    }

    for (int i = 1; i <= m; i++)
    {
        int j = pq.top().se;
        pq.pop();

        cout << mn[j].fi << '\n';

        Upd(-1, mn[j].se, root[j]);
        mn[j] = Get(j, vt[j], root[j]);
        pq.push({mn[j].fi, j});
    }
}

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