#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
using namespace std;
const ll mxn=3e5+5,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e9,mod=998244353;
/*
find k cheapest road
we can get the cheapest road for i node with sparse seg?
persist sparse segtee ??TT
*/
int n,k;
struct node{
pii val;
node*l,*r;
node():val({inf,inf}),l(0),r(0){};
};
map<int,vector<int>>mp;
map<int,int>cnt[mxn+10];
struct persist{
node *root[mxn+10];
pii get(node *x){return (x==NULL)?make_pair(inf,0):x->val;}
void update(int l,int r,node *last,node *&cur,int pos,int val){
if(last==NULL)cur=new node();
else cur=new node(*last);
if(l==r)return void(cur->val={val,pos});
int mid=l+(r-l)/2;
if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val);
else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val);
cur->val=min(get(cur->l),get(cur->r));
}
pii qry(int l,int r,node *cur,int ql,int qr){
if(cur==NULL||l>qr||r<ql)return {inf,0};
if(ql<=l&&r<=qr)return cur->val;
int mid=l+(r-l)/2;
return min(qry(l,mid,cur->l,ql,qr),qry(mid+1,r,cur->r,ql,qr));
}
}t,t2;
void show(){
cout<<"PPPP\n";
for(int i=0;i<n;i++){
for(int j=0;j<=0;j++)cout<<t.qry(nx,mx,t.root[i],j,j).f<<" ";
cout<<'\n';
}
}
int32_t main(){
fastio
cin>>n>>k;
vector<pii>v(n);
for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s,t.root[i]=new node(),t2.root[i]=new node();
sort(all(v));
for(int i=0;i<n;i++)mp[v[i].s].pb(i);
for(int i=1;i<n;i++){
//update the last one
t.update(nx,mx,t.root[i-(i!=0)],t.root[i],v[i-1].s,-v[i-1].f+v[i-1].s);
t2.update(nx,mx,t2.root[i-(i!=0)],t2.root[i],v[i-1].s,-v[i-1].f-v[i-1].s);
}
auto del=[&](int x,int pos){
if(cnt[x].find(pos)==cnt[x].end())cnt[x][pos]=upper_bound(all(mp[pos]),x-1)-mp[pos].begin()-1;
cnt[x][pos]--;
return (cnt[x][pos]<0)?inf:v[cnt[x][pos]].f;
};
auto get=[&](int x){
pii a=t.qry(nx,mx,t.root[x],v[x].s,mx),b=t2.qry(nx,mx,t2.root[x],nx,v[x].s-1);
ll up;
if(a.f-v[x].s<b.f+v[x].s){
up=del(x,a.s);
if(up!=inf){
t.update(nx,mx,t.root[x],t.root[x],a.s,-up+a.s);
t2.update(nx,mx,t2.root[x],t2.root[x],a.s,-up-a.s);
}
else t.update(nx,mx,t.root[x],t.root[x],a.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],a.s,inf);
return v[x].f+a.f-v[x].s;
}
else{
up=del(x,b.s);
if(up!=inf){
t.update(nx,mx,t.root[x],t.root[x],b.s,-up+b.s);
t2.update(nx,mx,t2.root[x],t2.root[x],b.s,-up-b.s);
}
else t.update(nx,mx,t.root[x],t.root[x],b.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],b.s,inf);
return v[x].f+b.f+v[x].s;
}
};
priority_queue<pii,vector<pii>,greater<pii>>pq;
for(int i=0;i<n;i++)pq.push({get(i),i});
for(int i=0;i<k;i++){
if(pq.empty())assert(0);
cout<<pq.top().f<<'\n';
int x=pq.top().s;
pq.pop();
pq.push({get(x),x});
}
}
/*
3 3
-1 0
0 2
0 0
5 4
1 -1
2 0
-1 0
0 2
0 -2
4 6
0 0
1 0
3 0
4 0
*/
Compilation message
road_construction.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
road_construction.cpp:45:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
45 | node():val({inf,inf}),l(0),r(0){};
| ^
road_construction.cpp:51:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
51 | pii get(node *x){return (x==NULL)?make_pair(inf,0):x->val;}
| ^
road_construction.cpp:52:66: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
52 | void update(int l,int r,node *last,node *&cur,int pos,int val){
| ^
road_construction.cpp:61:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
61 | pii qry(int l,int r,node *cur,int ql,int qr){
| ^
road_construction.cpp:68:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
68 | void show(){
| ^
road_construction.cpp:75:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
75 | int32_t main(){
| ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:87:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
87 | auto del=[&](int x,int pos){
| ^
road_construction.cpp:92:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
92 | auto get=[&](int x){
| ^
road_construction.cpp: In lambda function:
road_construction.cpp:101:57: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
101 | else t.update(nx,mx,t.root[x],t.root[x],a.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],a.s,inf);
| ^~~
road_construction.cpp:101:104: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
101 | else t.update(nx,mx,t.root[x],t.root[x],a.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],a.s,inf);
| ^~~
road_construction.cpp:110:57: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
110 | else t.update(nx,mx,t.root[x],t.root[x],b.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],b.s,inf);
| ^~~
road_construction.cpp:110:104: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
110 | else t.update(nx,mx,t.root[x],t.root[x],b.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],b.s,inf);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
651 ms |
777492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2029 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2449 ms |
1593024 KB |
Output is correct |
| 2 |
Correct |
2454 ms |
1588924 KB |
Output is correct |
| 3 |
Correct |
2 ms |
16988 KB |
Output is correct |
| 4 |
Correct |
1300 ms |
1519240 KB |
Output is correct |
| 5 |
Correct |
1562 ms |
1562432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2449 ms |
1593024 KB |
Output is correct |
| 2 |
Correct |
2454 ms |
1588924 KB |
Output is correct |
| 3 |
Correct |
2 ms |
16988 KB |
Output is correct |
| 4 |
Correct |
1300 ms |
1519240 KB |
Output is correct |
| 5 |
Correct |
1562 ms |
1562432 KB |
Output is correct |
| 6 |
Incorrect |
2517 ms |
1588932 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
651 ms |
777492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
651 ms |
777492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
