Submission #1157967

#TimeUsernameProblemLanguageResultExecution timeMemory
1157967dibamboo23Road Construction (JOI21_road_construction)C++20
13 / 100
1886 ms429576 KiB
/* author : Dinmukhammed ^_^ */ #include <bits/stdc++.h> using namespace std; #define F first #define S second #define sz size() #define ll long long #define ld long double #define int ll const int N=6e5+3; const ll inf=1e18; const ll MOD=1e9+7; ll t[N*60],L[N*60],R[N*60]; int iddd=0; int n; int copy(int v){ int nv=++iddd; t[nv]=t[v]; L[nv]=L[v]; R[nv]=R[v]; return nv; } int build(int tl=1,int tr=n+n){ int v=++iddd; t[v]=inf; if(tl==tr)return v; int md=(tl+tr)>>1; L[v]=build(tl,md); R[v]=build(md+1,tr); return v; } int upd(int pos,ll x,int v,int tl=1,int tr=n+n){ v=copy(v); if(tl==tr){ t[v]=x; return v; } int md=(tl+tr)>>1; if(pos<=md)L[v]=upd(pos,x,L[v],tl,md); else R[v]=upd(pos,x,R[v],md+1,tr); t[v]=min(t[L[v]],t[R[v]]); return v; } ll get(int l,int r,int v,int tl=1,int tr=n+n){ if(tl>=l&&tr<=r)return t[v]; if(tl>r||l>tr)return inf; int md=(tl+tr)>>1; return min(get(l,r,L[v],tl,md),get(l,r,R[v],md+1,tr)); } int del(ll x,int v,int tl=1,int tr=n+n){ v=copy(v); if(tl==tr){ t[v]=inf; return v; } int md=(tl+tr)>>1; if(t[R[v]]!=x)L[v]=del(x,L[v],tl,md); else R[v]=del(x,R[v],md+1,tr); t[v]=min(t[L[v]],t[R[v]]); return v; } int x[N],y[N],hh[N]; bool cmp(int i,int j){ return x[i]<x[j]; } void Main(){ int k;cin>>n>>k; vector<int>st1,pos; for(int i=1;i<=n;i++)cin>>x[i]>>y[i],st1.push_back(y[i]),pos.push_back(i); sort(st1.begin(),st1.end()); map<int,int>mp; int id=0; for(int i=0;i<n;i++){ if(i==0||st1[i]!=st1[i-1])mp[st1[i]]=id; id++; } sort(pos.begin(),pos.end(),cmp); set<pair<ll,int>>st; id=0; vector<int>root1={build()}; vector<int>root2={build()}; for(auto i:pos){ // cout<<x[i]<<" "<<y[i]<<" "; mp[y[i]]++; int h=mp[y[i]]; // cout<<h<<"\n"; hh[id]=h; ll val=min(get(1,h,root1.back())+(ll)x[i]+(ll)y[i],get(h,n+n,root2.back())+(ll)x[i]-(ll)y[i]); st.insert({val,id}); root1.push_back(upd(h,-(ll)x[i]-(ll)y[i],root1.back())); root2.push_back(upd(h,-(ll)x[i]+(ll)y[i],root2.back())); id++; } // cout<<"\n"; // for(auto to:st)cout<<to.F<<" "<<to.S<<"\n"; // cout<<"\n"; while(k--){ cout<<st.begin()->F<<"\n"; int v=st.begin()->S; ll val=st.begin()->F; st.erase(st.begin()); int i=pos[v]; ll val1=get(1,hh[v],root1[v]); ll val2=get(hh[v],n+n,root2[v]); if(val==val2+(ll)x[i]-(ll)y[i]){ // cout<<"2"; root2[v]=del(val2,root2[v]); val2=get(hh[v],n+n,root2[v]); } else{ // cout<<"1"; root1[v]=del(val1,root1[v]); val1=get(1,hh[v],root1[v]); } // cout<<val1<<" "<<val2<<"\n"; if(min(val,val1)==inf)continue; ll res=min(val1+(ll)x[i]+(ll)y[i],val2+(ll)x[i]-(ll)y[i]); // cout<<res<<" "<<v<<"\n"; st.insert({res,v}); } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int tt=1; // cin>>tt; while(tt--)Main(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...