#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000];
pair<ll,ll> p[1100000];
vector<ll> seg1[550000],seg2[550000];
vector<ll> tmp,ans,v,u;
void add()
{
ll i;
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
// printf("!");
merge(ans.begin(),ans.end(),v.begin(),v.end(),tmp.begin());
// printf("?");
for(i=0;i<k;i++)
{
ans[i]=tmp[i];
}
}
void f1(ll x)
{
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(seg1[x*2].begin(),seg1[x*2].end(),seg1[x*2+1].begin(),seg1[x*2+1].end(),tmp.begin());
ll i;
for(i=0;i<k;i++)
{
seg1[x][i]=tmp[i];
}
if(x==1)
return;
f1(x/2);
}
void f2(ll x)
{
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(seg2[x*2].begin(),seg2[x*2].end(),seg2[x*2+1].begin(),seg2[x*2+1].end(),tmp.begin());
ll i;
for(i=0;i<k;i++)
{
seg2[x][i]=tmp[i];
}
if(x==1)
return;
f2(x/2);
}
vector<ll> g1(ll x,ll y,ll z)
{
vector<ll> cur;
cur.resize(k);
fill(cur.begin(),cur.end(),inf);
if(y<l||x>r)
return cur;
if(l<=x&&y<=r)
return seg1[z];
vector<ll> v1,v2;
v1=g1(x,(x+y)/2,z*2);
v2=g1((x+y)/2+1,y,z*2+1);
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
ll u,i;
for(i=0;i<k;i++)
{
cur[i]=tmp[i];
}
return cur;
}
vector<ll> g2(ll x,ll y,ll z)
{
vector<ll> cur;
cur.resize(k);
fill(cur.begin(),cur.end(),inf);
if(y<l||x>r)
return cur;
if(l<=x&&y<=r)
return seg2[z];
vector<ll> v1,v2;
v1=g2(x,(x+y)/2,z*2);
v2=g2((x+y)/2+1,y,z*2+1);
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
ll u,i;
for(i=0;i<k;i++)
{
cur[i]=tmp[i];
}
return cur;
}
ll tr(ll x)
{
return lower_bound(u.begin(),u.end(),x)-u.begin()+1;
}
int main()
{
scanf("%lld %lld",&n,&k);
ans.resize(k);
fill(ans.begin(),ans.end(),inf);
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&x,&y);
p[i]={x,y};
u.push_back(y);
}
sort(u.begin(),u.end());
u.erase(unique(u.begin(),u.end()),u.end());
sort(p+1,p+n+1);
// printf("!");
for(i=1;i<=524288;i++)
{
seg1[i].resize(k);
seg2[i].resize(k);
fill(seg1[i].begin(),seg1[i].end(),inf);
fill(seg2[i].begin(),seg2[i].end(),inf);
}
for(i=1;i<=n;i++)
{
// printf("%lld\n",i);
x=p[i].first;
y=p[i].second;
z=tr(y);
l=z;
r=262144;
v=g1(1,262144,1);
for(j=0;j<v.size();j++)
{
v[j]+=x-y;
}
// printf("?");
add();
// printf("!");
l=1;
r=z-1;
v=g2(1,262144,1);
for(j=0;j<v.size();j++)
{
v[j]+=x+y;
}
//printf("@");
add();
seg1[z+262143].push_back(y-x);
seg2[z+262143].push_back(-y-x);
sort(seg1[z+262143].begin(),seg1[z+262143].end());
seg1[z+262143].erase(--seg1[z+262143].end());
sort(seg2[z+262143].begin(),seg2[z+262143].end());
seg2[z+262143].erase(--seg2[z+262143].end());
f1((z+262143)/2);
f2((z+262143)/2);
}
//printf("\n\n\n\n%lld\n",ans.size());
for(i=0;i<k;i++)
{
// printf("!");
printf("%lld\n",ans[i]);
}
}
Compilation message
road_construction.cpp: In function 'std::vector<long long int> g1(ll, ll, ll)':
road_construction.cpp:69:8: warning: unused variable 'u' [-Wunused-variable]
69 | ll u,i;
| ^
road_construction.cpp: In function 'std::vector<long long int> g2(ll, ll, ll)':
road_construction.cpp:92:8: warning: unused variable 'u' [-Wunused-variable]
92 | ll u,i;
| ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:134:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(j=0;j<v.size();j++)
| ~^~~~~~~~~
road_construction.cpp:144:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(j=0;j<v.size();j++)
| ~^~~~~~~~~
road_construction.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%lld %lld",&n,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~
road_construction.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%lld %lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1035 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
968 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1944 ms |
71260 KB |
Output is correct |
| 2 |
Correct |
1898 ms |
71104 KB |
Output is correct |
| 3 |
Correct |
55 ms |
59988 KB |
Output is correct |
| 4 |
Correct |
341 ms |
69072 KB |
Output is correct |
| 5 |
Correct |
1115 ms |
71524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1944 ms |
71260 KB |
Output is correct |
| 2 |
Correct |
1898 ms |
71104 KB |
Output is correct |
| 3 |
Correct |
55 ms |
59988 KB |
Output is correct |
| 4 |
Correct |
341 ms |
69072 KB |
Output is correct |
| 5 |
Correct |
1115 ms |
71524 KB |
Output is correct |
| 6 |
Correct |
3421 ms |
179880 KB |
Output is correct |
| 7 |
Correct |
3375 ms |
179840 KB |
Output is correct |
| 8 |
Correct |
120 ms |
125768 KB |
Output is correct |
| 9 |
Correct |
113 ms |
125652 KB |
Output is correct |
| 10 |
Correct |
3338 ms |
174852 KB |
Output is correct |
| 11 |
Correct |
523 ms |
134848 KB |
Output is correct |
| 12 |
Correct |
1524 ms |
137408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1035 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1035 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
