Submission #788054

#	Time	Username	Problem	Language	Result	Execution time	Memory
788054		winter0101	Road Construction (JOI21_road_construction)	C++14	100 / 100	2302 ms	509264 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+5e4+9;
const int inf=2e9+1;
struct node {
int l,r;
pii val;
node(){
val.fi=inf;
val.se=0;
}
}st[30000009];
int rev[maxn];
pii combine(const pii &p, const pii &q){
if (p.fi<q.fi)return p;
return q;
}
int nnode=0;
int build(int l,int r){
int newnode=++nnode;
st[newnode].val.se=l;
if (l==r)return newnode;
int mid=(l+r)/2;
st[newnode].l=build(l,mid);
st[newnode].r=build(mid+1,r);
return newnode;
}
int copy(int id){
    st[++nnode]=st[id];
    return nnode;
}
int update(int id,int l,int r,int u,int val){
if (l>u||r<u)return id;
if (l==r){
    int newnode=copy(id);
    st[newnode].val.fi=val;
    st[newnode].val.se=rev[l];
    return newnode;
}
int newnode=copy(id);
int mid=(l+r)/2;
st[newnode].l=update(st[id].l,l,mid,u,val);
st[newnode].r=update(st[id].r,mid+1,r,u,val);
st[newnode].val=combine(st[st[newnode].l].val,st[st[newnode].r].val);
return newnode;
}
pii get(int id,int l,int r,int u,int v){
 if (l>v||r<u||u>v)return node().val;
 if (u<=l&&r<=v)return st[id].val;
 int mid=(l+r)/2;
 return combine(get(st[id].l,l,mid,u,v),get(st[id].r,mid+1,r,u,v));
}
pii a[maxn];
int n,k;
vector<int>posy;
vector<int> posfory(){
vector<pii>b;
b.resize(n+1);
for1(i,1,n){
b[i].se=i;
b[i].fi=a[i].se;
//cout<<a[i].se<<" "<<i<<'\n';
}
sort(b.begin()+1,b.end());
vector<int>sorting;
sorting.resize(n+1);
for1(i,1,n){
//cout<<b[i].fi<<" "<<b[i].se<<'\n';
sorting[b[i].se]=i;
rev[i]=b[i].se;
}
return sorting;
}
struct edg{
int u,v;
long long val;
bool operator < (const edg &p)const {
if (val==p.val&&u!=p.u)return u<p.u;
if (val==p.val&&u==p.u)return v<p.v;
return val<p.val;
}
};
int c[maxn],d[maxn];
//c for smaller
//d for greater
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>k;
    for1(i,1,n){
    cin>>a[i].fi>>a[i].se;
    }
    sort(a+1,a+1+n);
    posy=posfory();
    //for1(i,1,n)cout<<posy[i]<<" "<<rev[posy[i]]<<'\n';
    //for1(i,1,n)cout<<a[i].fi<<' '<<a[i].se<<'\n';
    //return 0;
    multiset<edg>choose;
    int sml=build(1,n),grt=sml;
    for1(i,1,n){
    if (i==1){
    sml=update(sml,1,n,posy[i],-a[i].fi-a[i].se);
    grt=update(grt,1,n,posy[i],-a[i].fi+a[i].se);
    }
    else {
    //choose xi>xj yi>yj
    auto v=get(sml,1,n,1,posy[i]-1);
    //cout<<v.fi<<" "<<v.se<<'\n';
    if (v.fi<inf){
        choose.insert({i,v.se,1ll*v.fi+a[i].fi+a[i].se});
        c[i]=update(sml,1,n,posy[v.se],inf);
    }
    //end
    //choose xi>xj yi<yj
    auto u=get(grt,1,n,posy[i]+1,n);
    if (u.fi<inf){
        choose.insert({i,u.se,1ll*u.fi+a[i].fi-a[i].se});
        d[i]=update(grt,1,n,posy[u.se],inf);
    }
    //cout<<i<<" "<<u.se<<" "<<v.se<<" "<<u.fi<<" "<<v.fi<<'\n';
    //end
    sml=update(sml,1,n,posy[i],-a[i].fi-a[i].se);
    grt=update(grt,1,n,posy[i],-a[i].fi+a[i].se);
    }
    }
    //cout<<sz(choose)<<'\n';
    //for (auto u:choose)cout<<u.u<<" "<<u.v<<" "<<u.val<<'\n';
    for1(i,1,k){
    auto best=*(choose.begin());
    choose.erase(choose.begin());
    //cerr<<best.u<<" "<<best.v<<" "<<best.val<<'\n';
    cout<<best.val<<'\n';
    /*long long ans;
    cin>>ans;
    if (ans!=best.val){
        cout<<ans<<" "<<best.val<<" "<<i<<'\n';
        return 0;
    }*/
    int u=best.u,v=best.v;
    if (a[u].se<a[v].se){
        //grt
        auto newv=get(d[u],1,n,posy[u]+1,n);
        if (newv.fi>=inf)continue;
        choose.insert({u,newv.se,1ll*newv.fi+a[u].fi-a[u].se});
        d[u]=update(d[u],1,n,posy[newv.se],inf);
    }
    else {
        //sml
        auto newv=get(c[u],1,n,1,posy[u]-1);
        if (newv.fi>=inf)continue;
        choose.insert({u,newv.se,1ll*newv.fi+a[u].fi+a[u].se});
        c[u]=update(c[u],1,n,posy[newv.se],inf);
    }
    }
}

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