| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1278027 | denislav | Road Construction (JOI21_road_construction) | C++20 | 0 ms | 0 KiB |
# include <iostream>
# include <vector>
# include <algorithm>
# include <queue>
# include <tuple>
using namespace std;
const long long INF=(long long)4e9+11;
const int MAX=250000+11,LOG=20;
int n,K;
pair<int,int> a[MAX];
int orderP[MAX];
int orderM[MAX];
int real_val[MAX*2];
int ct;
int roots[MAX][LOG];
int tree[MAX*LOG*LOG*2];
int lv[MAX*LOG*LOG*2];
int rv[MAX*LOG*LOG*2];
int update(int pos, int d, int v, int l=1, int r=n*2)
{
if(l==r)
{
ct++;
tree[ct]=tree[v]+d;
return ct;
}
int mid=(l+r)/2;
if(pos<=mid)
{
ct++;
int v2=ct;
lv[v2]=update(pos,d,lv[v],l,mid);
rv[v2]=rv[v];
tree[v2]=tree[lv[v2]]+tree[rv[v2]];
return v2;
}
else
{
ct++;
int v2=ct;
lv[v2]=lv[v];
rv[v2]=update(pos,d,rv[v],mid+1,r);
tree[v2]=tree[lv[v2]]+tree[rv[v2]];
return v2;
}
}
long long walk(int k, int v, int l=1, int r=n*2)
{
if(l==r) return real_val[l];
int mid=(l+r)/2;
if(tree[lv[v]]>=k) return walk(k,lv[v],l,mid);
else return walk(k-tree[lv[v]],rv[v],mid+1,r);
}
int roots_under[MAX][LOG];
int cnt_under[MAX][LOG];
int roots_over[MAX][LOG];
int cnt_over[MAX][LOG];
void cdq(int l, int r, int level)
{
if(l==r) return ;
//cout<<"Enter:"<<l<<" "<<r<<" "<<level<<endl;
int mid=(l+r)/2;
vector<pair<int,int>> LS,RS;
for(int i=l;i<=mid;i++) LS.push_back({a[i].second,i});
for(int i=mid+1;i<=r;i++) RS.push_back({a[i].second,i});
sort(LS.begin(),LS.end());
sort(RS.begin(),RS.end());
int under=0,over=0;
for(int i=mid+1;i<=r;i++) over=update(orderP[i],1,over);
int ptr=0;
for(pair<int,int> PA: LS)
{
int id=PA.second;
while(ptr<(int)RS.size() and a[id].second>RS[ptr].first)
{
under=update(orderM[RS[ptr].second],1,under);
over=update(orderP[RS[ptr].second],-1,over);
ptr++;
}
roots_under[id][level]=under;
roots_over[id][level]=over;
}
//cout<<"Pass:"<<l<<" "<<r<<" "<<level<<endl;
cdq(l,mid,level+1);
cdq(mid+1,r,level+1);
}
tuple<long long,int,int> ans;
void dc(int l, int r, int level, int idx)
{
if(l==r) return ;
int mid=(l+r)/2;
if(l<=mid)
{
if(cnt_under[idx][level]+1<=tree[roots_under[idx][level]])
ans=min(ans,make_tuple(walk(cnt_under[idx][level]+1,roots_under[idx][level])+a[idx].second-a[idx].first,level,0));
if(cnt_over[idx][level]+1<=tree[roots_over[idx][level]])
ans=min(ans,make_tuple(walk(cnt_over[idx][level]+1,roots_over[idx][level])-a[idx].second-a[idx].first,level,1));
}
if(idx<=mid) dc(l,mid,level+1,idx);
else dc(mid+1,r,level+1,idx);
}
long long get_best(int idx)
{
ans={INF,INF,INF};
dc(1,n,0,idx);
long long sc;
int level,type;
tie(sc,level,type)=ans;
if(sc==INF) return INF;
if(type==0) cnt_under[idx][level]++;
else cnt_over[idx][level]++;
return sc;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
vector<pair<int,int>> compr;
for(int i=1;i<=n;i++)
{
compr.push_back({a[i].first+a[i].second,i});
compr.push_back({a[i].first-a[i].second,-i});
}
sort(compr.begin(),compr.end());
for(int i=0;i<n*2;i++)
{
int id=compr[i].second;
if(id>0)
{
orderP[id]=i+1;
real_val[i+1]=compr[i].first;
}
else
{
orderM[-id]=i+1;
real_val[i+1]=compr[i].first;
}
}
cdq(1,n,0);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
for(int i=1;i<=n;i++) pq.push({get_best(i),i});
for(int tt=1;tt<=K;tt++)
{
long long sc;
int idx;
tie(sc,idx)=pq.top();
pq.pop();
cout<<sc<<"\n";
pq.push({get_best(idx),idx});
}
return 0;
}