Submission #1197714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197714		Hanksburger	Road Construction (JOI21_road_construction)	C++20	100 / 100	4085 ms	1570060 KiB

road_construction

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    node *lc, *rc;
    int l, r;
    pair<int, int> val;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), val({1e18, 0}) {}
} *empt, *lft[250005], *rght[250005], *root[750005];
set<pair<int, pair<int, int> > > s;
int lvers[250005], rvers[250005];
pair<int, int> points[250005];
vector<pair<int, int> > vec;
void build(node *i)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    i->lc=new node(i->l, mid);
    i->rc=new node(mid+1, i->r);
    build(i->lc);
    build(i->rc);
}
void upd1(node *pre, node *i, int x, int y)
{
    if (i->l==i->r)
    {
        i->val={y, x};
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        i->lc=new node(i->l, mid);
        upd1(pre->lc, i->lc, x, y);
        i->rc=pre->rc;
    }
    else
    {
        i->lc=pre->lc;
        i->rc=new node(mid+1, i->r);
        upd1(pre->rc, i->rc, x, y);
    }
    i->val=min(i->lc->val, i->rc->val);
}
void upd2(node *em, node *pre, node *i, int x)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        i->lc=new node(i->l, mid);
        upd2(em->lc, pre->lc, i->lc, x);
        i->rc=em->rc;
    }
    else
    {
        i->lc=pre->lc;
        i->rc=new node(mid+1, i->r);
        upd2(em->rc, pre->rc, i->rc, x);
    }
    i->val=min(i->lc->val, i->rc->val);
}
void upd3(node *em, node *pre, node *i, int x)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        i->lc=new node(i->l, mid);
        upd3(em->lc, pre->lc, i->lc, x);
        i->rc=pre->rc;
    }
    else
    {
        i->lc=em->lc;
        i->rc=new node(mid+1, i->r);
        upd3(em->rc, pre->rc, i->rc, x);
    }
    i->val=min(i->lc->val, i->rc->val);
}
int dist(int x, int y)
{
    return abs(points[x].first-points[y].first)+abs(points[x].second-points[y].second);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, cur;
    cin >> n >> k;
    for (int i=1; i<=n; i++)
        cin >> points[i].first >> points[i].second;
    sort(points+1, points+n+1);
    for (int i=1; i<=n; i++)
        vec.push_back({-points[i].second, i});
    sort(vec.begin(), vec.end());
    empt=lft[0]=rght[0]=new node(1, n);
    build(empt);
    for (int i=1; i<=n; i++)
    {
        int x=vec[i-1].second;
        lft[i]=new node(1, n);
        rght[i]=new node(1, n);
        upd1(lft[i-1], lft[i], x, points[x].second-points[x].first);
        upd1(rght[i-1], rght[i], x, points[x].first+points[x].second);
        root[i*2-1]=new node(1, n);
        root[i*2]=new node(1, n);
        upd2(empt, lft[i-1], root[i*2-1], x);
        upd3(empt, rght[i-1], root[i*2], x);
        lvers[x]=i*2-1;
        rvers[x]=i*2;
        if ((root[i*2-1]->val).first<1e15)
        {
            int y=(root[i*2-1]->val).second;
            s.insert({dist(x, y), {x, y}});
            //cout << "left x y " << x << ' ' << y << '\n';
        }
        if ((root[i*2]->val).first<1e15)
        {
            int y=(root[i*2]->val).second;
            s.insert({dist(x, y), {x, y}});
            //cout << "right x y " << x << ' ' << y << '\n';
        }
    }
    cur=n*2;
    while (k--)
    {
        cout << (s.begin()->first) << '\n';
        int x=(s.begin()->second).first, y=(s.begin()->second).second;
        //cout << "s element " << (s.begin()->first) << ' ' << x << ' ' << y << '\n';
        s.erase(s.begin());
        if (x<y)
        {
            cur++;
            root[cur]=new node(1, n);
            upd1(root[rvers[x]], root[cur], y, 1e18);
            rvers[x]=cur;
            if ((root[cur]->val).first<1e15)
            {
                y=(root[cur]->val).second;
                s.insert({dist(x, y), {x, y}});
                //cout << "new right x y " << x << ' ' << y << '\n';
            }
        }
        else
        {
            cur++;
            root[cur]=new node(1, n);
            upd1(root[lvers[x]], root[cur], y, 1e18);
            lvers[x]=cur;
            if ((root[cur]->val).first<1e15)
            {
                y=(root[cur]->val).second;
                s.insert({dist(x, y), {x, y}});
                //cout << "new left x y " << x << ' ' << y << '\n';
            }
        }
    }
}

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