#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const int inf=2e9;
struct point{
int x,y;
};
bool cmp(point fr,point sc){
return fr.x<sc.x;
}
struct node{
int l,r;
pair<int,int> val;
};
node tree[100*MAXN];
int n,cnt,num,k,zero;
point p[MAXN];
vector< pair<int,int> > w;
map< pair<int,int> ,int> mp;
pair<int,int> ret[MAXN];
priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
pair<int,int> c;
int root[MAXN][2];
/// left <= >
/// right <= >
void add_node(int l,int r){
num++;
tree[num].l=l;
tree[num].r=r;
}
pair<int,int> combine(pair<int,int> fr,pair<int,int> sc){
if(fr.first<sc.first)return fr;
return sc;
}
pair<int,int> getmin(int v,int l,int r,int ll,int rr){
//cout<<v<<" "<<l<<" "<<r<<"\n";
if(ll>rr or v==0)return {inf,0};
if(l==ll and r==rr){
return tree[v].val;
}else{
int tt=(l+r)/2;
return combine( getmin(tree[v].l,l,tt,ll,min(tt,rr)) , getmin(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
}
}
int update(int v,int l,int r,int pos,int val){
//cout<<v<<" "<<l<<" "<<r<<"\n";
if(l==r){
add_node(0,0);
tree[num].val={val,l};
return num;
}else{
int tt=(l+r)/2;
int id;
if(pos<=tt){
id=update(tree[v].l,l,tt,pos,val);
add_node(id,tree[v].r);
}else{
id=update(tree[v].r,tt+1,r,pos,val);
add_node(tree[v].l,id);
}
tree[num].val=combine( tree[tree[num].l].val , tree[tree[num].r].val );
return num;
}
}
int mins(int pos){
int ls=getmin(root[pos][0],1,cnt,1,p[pos].y).first;
int lg=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first;
ls+=p[pos].x+ret[p[pos].y].first;
lg+=p[pos].x-ret[p[pos].y].first;
return min(ls,lg);
}
void erasemin(int pos){
int curr=mins(pos),ps;
if(curr == getmin(root[pos][0],1,cnt,1,p[pos].y).first + p[pos].x + ret[p[pos].y].first ){
ps=getmin(root[pos][0],1,cnt,1,p[pos].y).second;
root[pos][0]=update(root[pos][0],1,cnt,ps,inf);
return;
}
if(curr == getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first + p[pos].x - ret[p[pos].y].first ){
ps=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).second;
root[pos][1]=update(root[pos][1],1,cnt,ps,inf);
return;
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
w.push_back({p[i].y,i});
}
sort(w.begin(),w.end()); cnt=1;
for(int i=0;i<w.size();i++){
if(i>0 and w[i]!=w[i-1])cnt++;
mp[w[i]]=cnt; ret[cnt]=w[i];
}
for(int i=1;i<=n;i++){
p[i].y=mp[{p[i].y,i}];
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=cnt;i++){
zero=update(zero,1,cnt,i,inf);
}
root[0][0]=root[0][1]=zero;
for(int i=1;i<=n;i++){
root[i][0]=update(root[i-1][0],1,cnt,p[i].y,-p[i].x-ret[p[i].y].first);
root[i][1]=update(root[i-1][1],1,cnt,p[i].y,-p[i].x+ret[p[i].y].first);
}
for(int i=1;i<=n;i++){
erasemin(i);
q.push({mins(i),i});
}
for(int i=1;i<=k;i++){
c=q.top(); q.pop();
erasemin(c.second);
q.push({mins(c.second),c.second});
cout<<c.first<<"\n";
}
return 0;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<w.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
161104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10059 ms |
167604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
855 ms |
648608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
855 ms |
648608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
161104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
161104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
