제출 #990999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990999		12345678	Road Construction (JOI21_road_construction)	C++17	100 / 100	3447 ms	1553936 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, idxx;
pair<ll, ll> p[nx];
map<ll, vector<ll>> mp;
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;

struct persist
{
    struct node
    {
        pair<ll, ll> mn;
        node *l, *r;
        node(pair<ll, ll> mn={1e18, 0}): mn(mn), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx], srt[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, idx}, 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:make_pair((ll)1e18, (ll)0), (k->r)?k->r->mn:make_pair((ll)1e18, (ll)0));
    }
    pair<ll, ll> query(int l, int r, pnode k, int ql, int qr)
    {
        if (r<ql||qr<l|!k||qr<ql) return {1e18, 0};
        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++)
    {
        up.srt[i]=up.rt[i];
        dn.srt[i]=dn.rt[i];
        auto upq=up.query(-inf, inf, up.srt[i], p[i].second, inf);
        upq.first+=p[i].first-p[i].second;
        auto dnq=dn.query(-inf, inf, dn.srt[i], -inf, p[i].second-1);
        dnq.first+=p[i].first+p[i].second;
        auto tmp=min(upq, dnq);
        //printf("here %d %lld %lld\n", i, tmp.first, tmp.second);
        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);
        if (tmp.first<1e10)
        {
            if (tmp.second>=p[i].second) up.update(-inf, inf, up.srt[i], up.srt[i], tmp.second, 1e18);
            else dn.update(-inf, inf, dn.srt[i], dn.srt[i], tmp.second, 1e18);
            idxx=mp[tmp.second].back();
            pq.push({tmp.first, i, tmp.second, idxx});
        }
        mp[p[i].second].push_back(p[i].first);
    }
    for (int t=0; t<k; t++)
    {
        auto [w, idx, idxy, idxx]=pq.top();
        pq.pop();
        cout<<w<<'\n';
        auto itr=lower_bound(mp[idxy].begin(), mp[idxy].end(), idxx);
        if (itr!=mp[idxy].begin()) pq.push({w+*itr-*prev(itr), idx, idxy, *prev(itr)});
        auto upq=up.query(-inf, inf, up.srt[idx], p[idx].second, inf);
        upq.first+=+p[idx].first-p[idx].second;
        auto dnq=dn.query(-inf, inf, dn.srt[idx], -inf, p[idx].second-1);
        dnq.first+=+p[idx].first+p[idx].second;
        auto tmp=min(upq, dnq);
        if (tmp.first<1e10)
        {
            if (tmp.second>=p[idx].second) up.update(-inf, inf, up.srt[idx], up.srt[idx], tmp.second, 1e18);
            else dn.update(-inf, inf, dn.srt[idx], dn.srt[idx], tmp.second, 1e18);
            idxx=p[idx].first-(tmp.first-abs(p[idx].second-tmp.second));
            pq.push({tmp.first, idx, tmp.second, idxx});
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In member function 'std::pair<long long int, long long int> persist::query(int, int, persist::pnode, int, int)':
road_construction.cpp:37:21: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   37 |         if (r<ql||qr<l|!k||qr<ql) return {1e18, 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