#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <assert.h>
#include <set>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef pair<ii, int> pii;
typedef vector<ii> vii;
const int maxn1 = 3e5 + 5, maxn2 = 1e6 + 6;
ii coor[maxn1];
ll dist[maxn2];
struct cmp
{
bool operator()(const ii &a, const ii &b) const
{
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
};
set<ii, cmp> s;
ll get_manhattan_dist(int i, int j)
{
return abs(coor[i].first - coor[j].first) + abs(coor[i].second - coor[j].second);
}
ll get_manhattan_dist(ii p1, ii p2)
{
return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}
void solve_sub1(int n, int k)
{
int n_road = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
dist[n_road++] = get_manhattan_dist(i, j);
}
}
sort(dist, dist + n_road);
for (int i = 0; i < k; i++)
{
cout << dist[i] << "\n";
}
}
void solve_sub2(int n, ll k)
{
sort(coor, coor + n);
ll l = 1, r = coor[n - 1].first - coor[0].first;
while (l < r)
{
int m = (l + r) >> 1, l1 = 0;
ll cnt = 0;
for (int i = 0; i < n; i++)
{
while (l1 < i && get_manhattan_dist(l1, i) > m)
{
l1++;
}
cnt += i - l1;
}
if (cnt >= k)
{
r = m;
}
else
{
l = m + 1;
}
}
int n_road = 0, lp = 0;
for (int i = 0; i < n; i++)
{
while (lp < i && get_manhattan_dist(lp, i) >= l)
{
lp++;
}
for (int j = lp; j < i; j++)
{
dist[n_road++] = get_manhattan_dist(j, i);
}
}
for (int i = n_road; i < k; i++)
{
dist[i] = l;
}
sort(dist, dist + k);
for (int i = 0; i < k; i++)
{
cout << dist[i] << '\n';
}
}
bool check_enough(int n, ll k, ll m)
{
s.clear();
ll cnt = 0;
for (int i = 0; i < n; i++)
{
ii curr_p = {-1e10, coor[i].second - m};
while (true)
{
set<ii>::iterator it1 = s.upper_bound(curr_p);
if (it1 == s.end())
break;
curr_p = *it1;
if (curr_p.second > coor[i].second + m)
break;
if (curr_p.first < coor[i].first - m)
{
s.erase(it1);
continue;
}
if (get_manhattan_dist(curr_p, coor[i]) <= m)
{
cnt++;
if (cnt >= k)
return true;
}
}
s.insert(coor[i]);
}
return false;
}
void create_dist(int n, ll k, ll l)
{
s.clear();
ll n_road = 0;
for (int i = 0; i < n; i++)
{
ii curr_p = {-1e10, coor[i].second - l};
while (true)
{
set<ii>::iterator it1 = s.upper_bound(curr_p);
if (it1 == s.end())
break;
curr_p = *it1;
if (curr_p.second > coor[i].second + l)
break;
if (curr_p.first < coor[i].first - l)
{
s.erase(it1);
continue;
}
if (get_manhattan_dist(curr_p, coor[i]) < l)
{
dist[n_road++] = get_manhattan_dist(curr_p, coor[i]);
}
}
s.insert(coor[i]);
}
for (int i = n_road; i < k; i++)
{
dist[i] = l;
}
sort(dist, dist + k);
for (int i = 0; i < k; i++)
{
cout << dist[i] << "\n";
}
}
void solve_sub3(int n, int k)
{
sort(coor, coor + n);
ll l = 1, r = 1e10;
while (l < r)
{
int m = (l + r) >> 1;
if (check_enough(n, k, m))
{
r = m;
}
else
{
l = m + 1;
}
}
create_dist(n, k, l);
}
void solve()
{
int n, k;
cin >> n >> k;
bool all_y0 = 1;
for (int i = 0; i < n; i++)
{
cin >> coor[i].first >> coor[i].second;
all_y0 &= (coor[i].second == 0);
}
// if (n <= 1000)
// {
// solve_sub1(n, k);
// return;
// }
// if (all_y0)
// {
// solve_sub2(n, k);
// return;
// }
solve_sub3(n, k);
}
int main()
{
// freopen("input_text", "r", stdin);
// freopen("output_text", "w", stdout);
// ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t-- > 0)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
4812 KB |
Output is correct |
| 2 |
Correct |
361 ms |
4956 KB |
Output is correct |
| 3 |
Execution timed out |
10013 ms |
340 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
428 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
425 ms |
7372 KB |
Output is correct |
| 3 |
Execution timed out |
10022 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
756 ms |
12824 KB |
Output is correct |
| 2 |
Correct |
1121 ms |
9656 KB |
Output is correct |
| 3 |
Execution timed out |
10029 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
756 ms |
12824 KB |
Output is correct |
| 2 |
Correct |
1121 ms |
9656 KB |
Output is correct |
| 3 |
Execution timed out |
10029 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
4812 KB |
Output is correct |
| 2 |
Correct |
361 ms |
4956 KB |
Output is correct |
| 3 |
Execution timed out |
10013 ms |
340 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
4812 KB |
Output is correct |
| 2 |
Correct |
361 ms |
4956 KB |
Output is correct |
| 3 |
Execution timed out |
10013 ms |
340 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
