#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pii pair<int,int>
using namespace std;
const int N=3e5+5,mod=1e9+7,Inf=5e9+16;
int t,n,k,le_[50*N],ri_[50*N],pos[N][2],K,cur,root[N],ind[N],I[N];
pair<int,int> tree[50*N][2];
pair<int,int>p[N];
set<pair<int,int> > s;
vector<pair<int,int> > v;
vector<pair<int,pair<int,int> > > c;
void build(int u,int l,int r){
tree[u][0] = tree[u][1] = {Inf,l};
if(l==r) return;
le_[u]=++cur;
ri_[u]=++cur;
int mid=(l+r)/2;
build(le_[u],l,mid);
build(ri_[u],mid+1,r);
}
void update(int u,int ind,int l,int r,int val1,int val2){
if(l>ind || r<ind) return;
if(l==r) {
tree[cur][0]={val1,l};
tree[cur][1]={val2,l};
return;
}
int mid = (l+r)/2,x = cur;
le_[x]= le_[u];
ri_[x] = ri_[u];
if(ind<=mid) le_[x]=++cur;
else ri_[x]=++cur;
update(le_[u],ind,l,mid,val1,val2);
update(ri_[u],ind,mid+1,r,val1,val2);
tree[x][0]=min(tree[le_[x]][0],tree[ri_[x]][0]);
tree[x][1]=min(tree[le_[x]][1],tree[ri_[x]][1]);
// cout<<x<<"++"<<endl;
}
pair<int,int> getans(int u,int start,int end,int l,int r,int type){
if(l>end|| r<start) return {Inf,0};
if(start<=l && r<=end) {
return tree[u][type];}
int mid=(l+r)/2;
return min(getans(le_[u],start,end,l,mid,type) , getans(ri_[u],start,end,mid+1,r,type));
}
main(){
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin >> p[i].f>>p[i].s;
}
sort(p+1,p+n+1);
for(int i=1;i<=n;i++) {
int diff = p[i].s;
v.push_back({diff,i});
}
v.push_back({-5e9,0});
sort(v.begin(),v.end());
for(int i=1;i<=n;i++) {
ind[v[i].s] = i; //cout<<v[i].s<<" ++ "<<i<<endl;
// pos[i] = v[i].s;
}
cur=1;
root[1] = cur;
build(1,1,n);
for(int i=1;i<=n;i++) {
int l = 1,r=n,id = n+1;
while(l<=r){
int mid=(l+r)/2;
if(v[mid].f>=p[i].s) {
id = mid;
r=mid-1;
}else l=mid+1;
}
if(i-1)root[i] = ++cur;
I[i] = id-1;
// cout<<id<<endl; // - y[i] +y[j] < -y[j] + y[i] y[j] < y[i]
if(i-1)update(root[i-1],ind[i-1],1,n,-p[i-1].f-p[i-1].s,-p[i-1].f+p[i-1].s);
s.insert({min(getans(root[i],1,id-1,1,n,0).f +p[i].f+p[i].s,getans(root[i],id,n,1,n,1).f +p[i].f - p[i].s),i} );
// cout<<"++"<<getans(root[i],id,n,1,n,1).f +p[i].f - p[i].s<<" "<<getans(root[i],id,n,1,n,1).s<<endl;
}
while(k--){
pii c = *s.begin();
int i = c.s;
// int g1 = getans(root[c.s],1,I[c.s],1,n,0).f+p[i].f+p[i].s, g2 = getans(root[c.s],I[c.s]+1,n,1,n,1);
cout<<c.f<<endl;
s.erase(c);
int ind = 0;
if(getans(root[c.s],1,I[c.s],1,n,0).f+p[i].f+p[i].s < getans(root[c.s],I[c.s]+1,n,1,n,1).f +p[i].f-p[i].s ) ind =getans(root[c.s],1,I[c.s],1,n,0).s;
else ind = getans(root[c.s],I[c.s]+1,n,1,n,1).s;
int bef = root[c.s];
root[c.s] = ++cur;
update(bef,ind,1,n,Inf,Inf);
s.insert({min(getans(root[i],1,I[i],1,n,0).f +p[i].f+p[i].s,getans(root[i],I[i]+1,n,1,n,1).f +p[i].f - p[i].s),c.s});
//cout<<getans(root[i],1,I[i],1,n,0).f+p[i].f+p[i].s<<"++"<<getans(root[i],1,I[i],1,n,0).s<<endl;
}
}
Compilation message
road_construction.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
51 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1133 ms |
132452 KB |
Output is correct |
| 2 |
Correct |
1123 ms |
132568 KB |
Output is correct |
| 3 |
Incorrect |
1060 ms |
126596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1974 ms |
499408 KB |
Output is correct |
| 2 |
Correct |
1960 ms |
499536 KB |
Output is correct |
| 3 |
Correct |
639 ms |
127044 KB |
Output is correct |
| 4 |
Correct |
1337 ms |
499316 KB |
Output is correct |
| 5 |
Correct |
1362 ms |
499576 KB |
Output is correct |
| 6 |
Correct |
1341 ms |
499484 KB |
Output is correct |
| 7 |
Correct |
1398 ms |
498712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1367 ms |
275752 KB |
Output is correct |
| 2 |
Correct |
1346 ms |
280744 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1367 ms |
275752 KB |
Output is correct |
| 2 |
Correct |
1346 ms |
280744 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1133 ms |
132452 KB |
Output is correct |
| 2 |
Correct |
1123 ms |
132568 KB |
Output is correct |
| 3 |
Incorrect |
1060 ms |
126596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1133 ms |
132452 KB |
Output is correct |
| 2 |
Correct |
1123 ms |
132568 KB |
Output is correct |
| 3 |
Incorrect |
1060 ms |
126596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
