Submission #990981

#	Time	Username	Problem	Language	Result	Execution time	Memory
990981		12345678	Road Construction (JOI21_road_construction)	C++17	7 / 100	804 ms	513104 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=250005, inf=1e9;

ll n, k, res=1e18;
pair<ll, ll> p[nx];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

struct persist
{
    struct node
    {
        ll mn;
        node *l, *r;
        node(ll mn=1e18): mn(mn), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void update(int l, int r, pnode &k, pnode t, int idx, ll vl)
    {
        //printf("update %d %d\n", l, r);
        if (t) k=new node(*t);
        else k=new node();
        if (l==r) return k->mn=vl, void();
        ll md=l+(r-l)/2;
        if (idx<=md) update(l, md, k->l, t?t->l:0, idx, vl);
        else update(md+1, r, k->r, t?t->r:0, idx, vl);
        k->mn=min((k->l)?k->l->mn:1e18, (k->r)?k->r->mn:1e18);
    }
    ll query(int l, int r, pnode k, int ql, int qr)
    {
        if (r<ql||qr<l|!k) return 1e18;
        if (ql<=l&&r<=qr) return k->mn;
        ll md=l+(r-l)/2;
        return min(query(l, md, k->l, ql, qr), query(md+1, r, k->r, ql, qr));
    }
} up, dn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>p[i].first>>p[i].second;
    sort(p+1, p+n+1);
    for (int i=1; i<=n; i++)
    {
        //printf("here %d\n", i);
        res=min(res, up.query(-inf, inf, up.rt[i], p[i].second, inf)+p[i].first-p[i].second);
        res=min(res, dn.query(-inf, inf, dn.rt[i], -inf, p[i].second)+p[i].first+p[i].second);
        //printf("here %d\n", i);
        up.update(-inf, inf, up.rt[i+1], up.rt[i], p[i].second, -p[i].first+p[i].second);
        dn.update(-inf, inf, dn.rt[i+1], dn.rt[i], p[i].second, -p[i].first-p[i].second);
    }
    cout<<res;
}

Compilation message (stderr)

road_construction.cpp: In member function 'long long int persist::query(int, int, persist::pnode, int, int)':
road_construction.cpp:36:21: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   36 |         if (r<ql||qr<l|!k) return 1e18;
      |                   ~~^~

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