#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[15000009];
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=build(1,n);
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);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
237876 KB |
Output is correct |
| 2 |
Correct |
246 ms |
237880 KB |
Output is correct |
| 3 |
Correct |
224 ms |
237892 KB |
Output is correct |
| 4 |
Correct |
219 ms |
237892 KB |
Output is correct |
| 5 |
Correct |
230 ms |
236720 KB |
Output is correct |
| 6 |
Correct |
81 ms |
235308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
696 ms |
518452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1098 ms |
534560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1098 ms |
534560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
237876 KB |
Output is correct |
| 2 |
Correct |
246 ms |
237880 KB |
Output is correct |
| 3 |
Correct |
224 ms |
237892 KB |
Output is correct |
| 4 |
Correct |
219 ms |
237892 KB |
Output is correct |
| 5 |
Correct |
230 ms |
236720 KB |
Output is correct |
| 6 |
Correct |
81 ms |
235308 KB |
Output is correct |
| 7 |
Correct |
1356 ms |
254096 KB |
Output is correct |
| 8 |
Correct |
1291 ms |
254084 KB |
Output is correct |
| 9 |
Correct |
214 ms |
237944 KB |
Output is correct |
| 10 |
Correct |
626 ms |
253340 KB |
Output is correct |
| 11 |
Correct |
688 ms |
253168 KB |
Output is correct |
| 12 |
Correct |
460 ms |
253952 KB |
Output is correct |
| 13 |
Correct |
548 ms |
252536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
237876 KB |
Output is correct |
| 2 |
Correct |
246 ms |
237880 KB |
Output is correct |
| 3 |
Correct |
224 ms |
237892 KB |
Output is correct |
| 4 |
Correct |
219 ms |
237892 KB |
Output is correct |
| 5 |
Correct |
230 ms |
236720 KB |
Output is correct |
| 6 |
Correct |
81 ms |
235308 KB |
Output is correct |
| 7 |
Runtime error |
696 ms |
518452 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
