This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 250007
struct point
{
int x,y;
} arr[MAXN];
int n,k;
bool cmp1(point &a, point &b)
{
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
bool cmp2(point &a, point &b)
{
return a.y<b.y;
}
int dist(int a, int b)
{
int xx=arr[a].x-arr[b].x;
if (xx<0) xx*=-1;
int yy=arr[a].y-arr[b].y;
if (yy<0) yy*=-1;
return xx+yy;
}
priority_queue<int> qu;
int BSIZE=1000;
void check()
{
for (int q=0;q<n;q++)
{
for (int w=1;w<=BSIZE;w++)
{
if (q-w<0) break;
int dst=dist(q,q-w);
if (qu.size()<k) qu.push(dst);
else
{
if (dst<qu.top())
{
qu.pop();
qu.push(dst);
}
}
}
}
}
int main()
{
cin>>n>>k;
for (int q=0;q<n;q++) cin>>arr[q].x>>arr[q].y;
sort(arr,arr+n,cmp1);
check();
//sort(arr,arr+n,cmp2);
//check();
vector<int> vv;
while (!qu.empty())
{
vv.push_back(qu.top());
qu.pop();
}
reverse(vv.begin(),vv.end());
for (int q=0;q<vv.size();q++) cout<<vv[q]<<"\n";
}
Compilation message (stderr)
road_construction.cpp: In function 'void check()':
road_construction.cpp:36:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if (qu.size()<k) qu.push(dst);
| ~~~~~~~~~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int q=0;q<vv.size();q++) cout<<vv[q]<<"\n";
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |