#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<pair<ll, int> > s, d;
ll a[N], b[N];
int loc[N], w[N], rev[N];
vector<int> seg[N];
void build(int id, int l, int r){
if(l == r){
seg[id].push_back({w[l]});
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
int i1 = 0;
int i2 = 0;
while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
if(seg[id << 1][i1] < seg[id << 1 | 1][i2])
seg[id].push_back(seg[id << 1][i1++]);
else
seg[id].push_back(seg[id << 1 | 1][i2++]);
}
while(i1 < seg[id << 1].size())
seg[id].push_back(seg[id << 1][i1++]);
while(i2 < seg[id << 1 | 1].size())
seg[id].push_back(seg[id << 1 | 1][i2++]);
}
int n;
ll k;
struct Node{
Node *le, *ri;
int cnt = 0;
int query(int l, int r, int L, int R){
if(l > R || r < L) return 0;
if(L <= l && r <= R) return cnt;
int m = (l + r) >> 1;
return le -> query(l, m, L, R) + ri -> query(m + 1, r, L, R);
}
Node* update(int l, int r, int x){
if(l > x || r < x) return this;
Node* ret = new Node();
if(l == r){
ret -> cnt = 1;
return ret;
}
ret -> le = le;
ret -> ri = ri;
int m = (l + r) >> 1;
ret -> le = ret -> le -> update(l, m, x);
ret -> ri = ret -> ri -> update(m + 1, r, x);
ret -> cnt = ret -> le -> cnt + ret -> ri -> cnt;
return ret;
}
};
void buildd(Node* pnt, int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
pnt -> le = new Node();
pnt -> ri = new Node();
buildd(pnt -> le, l, m);
buildd(pnt -> ri, m + 1, r);
}
Node* tree[N];
vector<ll> ans;
void find(int id, int l, int r, int L, int R, int le, int ri, int x){
if(l > R || r < L) return;
if(L <= l && r <= R){
le = lower_bound(seg[id].begin(), seg[id].end(), le) - seg[id].begin();
for(int i = le; i < seg[id].size() && seg[id][i] <= ri; ++i)
ans.push_back(max(a[x] - a[seg[id][i]], abs(b[rev[x]] - b[rev[seg[id][i]]])));
return;
}
int m = (l + r) >> 1;
find(id << 1, l, m, L, R, le, ri, x);
find(id << 1 | 1, m + 1, r, L, R, le, ri, x);
return;
}
int l1[N], r1[N], l2[N], r2[N];
bool count(ll len, bool get){
ll cnt = 0;
l1[0] = 1;
r1[0] = 0;
l2[0] = 1;
r2[0] = 1;
for(int i = 1; i <= n; ++i){
l1[i] = l1[i - 1];
while(a[l1[i]] < a[i] - len)
++l1[i];
r1[i] = i - 1;
l2[i] = l2[i - 1];
while(b[l2[i]] < b[i] - len)
++l2[i];
r2[i] = r2[i - 1];
while(r2[i] + 1 <= n && b[r2[i] + 1] <= b[i] + len)
++r2[i];
}
for(int i = n; i > 1; --i){
// int l1 = lower_bound(a + 1, a + i, a[i] - len) - a;
// int r1 = i - 1;
// int l2 = lower_bound(b + 1, b + rev[i], b[rev[i]] - len) - b;
// int r2 = upper_bound(b + rev[i], b + n + 1, b[rev[i]] + len) - b - 1;
if(l1[i] > r1[i] || l2[rev[i]] > r2[rev[i]]) continue;
if(get)
find(1, 1, n, l2[rev[i]], r2[rev[i]], l1[i], r1[i], i);
else
cnt += tree[r2[rev[i]]]->query(1, n, l1[i], r1[i]) - tree[l2[rev[i]] - 1]->query(1, n, l1[i], r1[i]);
if(cnt >= k) return 0;
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int x, y, i = 1; i <= n; ++i){
cin>>x>>y;
s.push_back({x + y, i});
d.push_back({x - y, i});
}
sort(s.begin(), s.end());
sort(d.begin(), d.end());
for(int i = 1; i <= n; ++i){
a[i] = s[i - 1].ff;
loc[s[i - 1].ss] = i;
}
for(int i = 1; i <= n; ++i){
b[i] = d[i - 1].ff;
w[i] = loc[d[i - 1].ss];
rev[w[i]] = i;
}
build(1, 1, n);
tree[0] = new Node();
buildd(tree[0], 1, n);
for(int i = 1; i <= n; ++i)
tree[i] = tree[i - 1] -> update(1, n, w[i]);
ll len = 0;
for(int i = (int)log2(4'000'000'000.0/sqrt(n * 1.0)); i >= 0; --i)
if(count((1LL << i) | len, 0))
len |= 1LL << i;
count(len, 1);
sort(ans.begin(), ans.end());
++len;
while(ans.size() < k)
ans.push_back(len);
for(auto& x : ans)
cout<<x<<'\n';
}
Compilation message
road_construction.cpp: In function 'void build(int, int, int)':
road_construction.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:28:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(i1 < seg[id << 1].size())
| ~~~^~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(i2 < seg[id << 1 | 1].size())
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void find(int, int, int, int, int, int, int, int)':
road_construction.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = le; i < seg[id].size() && seg[id][i] <= ri; ++i)
| ~~^~~~~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:164:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
164 | while(ans.size() < k)
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
28988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1957 ms |
244568 KB |
Output is correct |
| 2 |
Correct |
1898 ms |
244632 KB |
Output is correct |
| 3 |
Incorrect |
60 ms |
28776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3017 ms |
239396 KB |
Output is correct |
| 2 |
Correct |
2895 ms |
239440 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23792 KB |
Output is correct |
| 4 |
Correct |
530 ms |
239412 KB |
Output is correct |
| 5 |
Correct |
4447 ms |
239380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3017 ms |
239396 KB |
Output is correct |
| 2 |
Correct |
2895 ms |
239440 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23792 KB |
Output is correct |
| 4 |
Correct |
530 ms |
239412 KB |
Output is correct |
| 5 |
Correct |
4447 ms |
239380 KB |
Output is correct |
| 6 |
Correct |
5773 ms |
239328 KB |
Output is correct |
| 7 |
Correct |
5715 ms |
239416 KB |
Output is correct |
| 8 |
Incorrect |
16 ms |
23884 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
28988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
28988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
