Submission #1109997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109997		tosivanmak	Road Construction (JOI21_road_construction)	C++17	100 / 100	2228 ms	399972 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

struct Persist{
    int seg[10000000],lc[10000000],rc[10000000];
    ll ptr=1;
    ll build(ll l, ll r){
        if(l==r){
            seg[ptr]=1e18,lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
        }
        else{
            ll mid=(l+r)>>1;
            ll curptr=ptr; ptr++;
            lc[curptr]=build(l,mid); rc[curptr]=build(mid+1,r);
            seg[curptr]=1e18;
            return curptr;
        }
    }
    ll upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[ptr]=val; lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
        }
        else{
            ll mid=(l+r)>>1;
            ll curp=ptr; ptr++;
            if(ul<=mid){
                lc[curp]=upd(ul,l,mid,val,lc[id]); rc[curp]=rc[id];
            }
            else{
                rc[curp]=upd(ul,mid+1,r,val,rc[id]); lc[curp]=lc[id];
            }
            seg[curp]=min(seg[lc[curp]],seg[rc[curp]]);
            return curp;
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(ql>qr)return 1e18;
        if(l>qr||r<ql)return 1e18;
        if(l>=ql&&r<=qr){
            return seg[id];
        }
        ll mid=(l+r)>>1;
        return min(qry(ql,qr,l,mid,lc[id]),qry(ql,qr,mid+1,r,rc[id]));
    }
    ll bs(ll l, ll r, ll k, ll id){
        if(l==r)return l;
        ll mid=(l+r)>>1;
        if(seg[lc[id]]==k)return bs(l,mid,k,lc[id]);
        return bs(mid+1,r,k,rc[id]);
    }
    ll find(ll ql, ll qr, ll l, ll r, ll id, ll k){
        if(ql>qr)return -1;
        if(l>qr||r<ql)return -1;
        if(l>=ql&&r<=qr){
            if(seg[id]!=k) return -1;
            return bs(l,r,k,id);
        }
        ll mid=(l+r)>>1;
        ll bruh=find(ql,qr,l,mid,lc[id],k);
        if(bruh!=-1)return bruh;
        bruh=find(ql,qr,mid+1,r,rc[id],k);
        return bruh;
    }
}st,st2;
struct THING{
    ll val,verx,very,insegpos;
    bool operator<(const THING& th)const{
        return val>th.val;
    }
};
priority_queue<THING>pq;
int version[250005][3];
int prevver,prevver2;
vector<pair<ll,ll> >disc;
ll pos(pair<ll,ll>x){
    return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll x[n+5],y[n+5];
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    vector<pair<ll,ll> >pts;
    for(int i=1;i<=n;i++)pts.push_back({x[i],y[i]});
    sort(pts.begin(),pts.end());
    for(int i=0;i<pts.size();i++){
        disc.push_back({pts[i].second,i});
    }
    sort(disc.begin(),disc.end());
    prevver=st.build(1,disc.size()); prevver2=st2.build(1,disc.size());
    for(int i=0;i<pts.size();i++){
        int xx=pts[i].first,yy=pts[i].second;
        version[i][1]=prevver; version[i][2]=prevver2;
        prevver=st.upd(pos(make_pair(yy,i)),1,disc.size(),-xx-yy,prevver);
        prevver2=st2.upd(pos(make_pair(yy,i)),1,disc.size(),-xx+yy,prevver2);
    }
    for(int i=0;i<pts.size();i++){
        int xx=pts[i].first,yy=pts[i].second;
        ll posi=pos(make_pair(yy,i));
        ll for1=st.qry(1,posi,1,disc.size(),version[i][1]);
        ll segtreebst=st.find(1,posi,1,disc.size(),version[i][1],for1);
        pq.push({for1+xx+yy,i,1,segtreebst});
        ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[i][2]);
        segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[i][2],for2);
        pq.push({for2+xx-yy,i,2,segtreebst});
    }
    for(int i=1;i<=k;i++){
        THING lol=pq.top();
        ll val=lol.val,verx=lol.verx,very=lol.very,insegpos=lol.insegpos;
        ll xx=pts[verx].first,yy=pts[verx].second;
        pq.pop();
        cout<<val<<'\n';
        ll posi=pos(make_pair(yy,verx));
        if(very==1){
            version[verx][very]=st.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
            ll for1=st.qry(1,posi,1,disc.size(),version[verx][1]);
            ll segtreebst=st.find(1,posi,1,disc.size(),version[verx][1],for1);
            pq.push({for1+xx+yy,verx,1,segtreebst});
        }
        else{
            version[verx][very]=st2.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
            ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[verx][2]);
            ll segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[verx][2],for2);
            pq.push({for2+xx-yy,verx,2,segtreebst});
        }
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:90:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<pts.size();i++){
      |                 ~^~~~~~~~~~~
road_construction.cpp:95:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<pts.size();i++){
      |                 ~^~~~~~~~~~~
road_construction.cpp:101:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<pts.size();i++){
      |                 ~^~~~~~~~~~~

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