#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 250005 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, k;
ii a[N], b[N];
int savee[N];
map<ii, int> mp;
// type1[id]: (-x - y), type2[id]: (-x + y)
vector<int> x, y;
vector<int> type1[524290], type2[524290];
vector<int> bit1[524290], bit2[524290];
int mini1[524290], mini2[524290];
void build(int id, int l, int r){
bit1[id].resize(r - l + 2), bit2[id].resize(r - l + 2);
if(l == r){
type1[id].pb(-b[l].fi - b[l].se);
type2[id].pb(-b[l].fi + b[l].se);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
for(auto it : type1[id << 1]) type1[id].pb(it);
for(auto it : type2[id << 1]) type2[id].pb(it);
for(auto it : type1[id << 1 | 1]) type1[id].pb(it);
for(auto it : type2[id << 1 | 1]) type2[id].pb(it);
sort(type1[id].begin(), type1[id].end());
sort(type2[id].begin(), type2[id].end());
type1[id].resize(unique(type1[id].begin(), type1[id].end()) - type1[id].begin());
type2[id].resize(unique(type2[id].begin(), type2[id].end()) - type2[id].begin());
bit1[id].resize(type1[id].size() + 1);
bit2[id].resize(type2[id].size() + 1);
}
void upd1(int id, int id2){
for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
}
int get1(int id, int id2){
int ans = 0;
for(; id2; id2 -= id2 & -id2){
ans += bit1[id][id2];
}
return ans;
}
void upd2(int id, int id2){
for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
}
int get2(int id, int id2){
int ans = 0;
for(; id2; id2 -= id2 & -id2){
ans += bit2[id][id2];
}
return ans;
}
int cnt;
ii point;
vector<ii> u1[N], u2[N];
void prep(int id, int l, int r, int pos){
int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
u1[cnt].pb({id, posi});
posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
u2[cnt].pb({id, posi});
//upd1(id, posi);
//upd2(id, posi);
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) prep(id << 1, l, mid, pos);
else prep(id << 1 | 1, mid + 1, r, pos);
}
/*
void upd(int id, int l, int r, int pos){
//int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
//int posi = 1;
upd1(id, posi);
//posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
upd2(id, posi);
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) upd(id << 1, l, mid, pos);
else upd(id << 1 | 1, mid + 1, r, pos);
}*/
int type, val;
vector<int> g1[N], g2[N];
vector<int> min_val1[524290], min_val2[524290];
vector<int> min_val3[524290], min_val4[524290];
void prep2(int id, int l, int r, int L, int R){// <= val, return no of pairs
if(l > R || r < L) return;
if(l >= L && r <= R){
if(!type){
g1[cnt].pb(id);
min_val1[id].pb(a[cnt].fi + a[cnt].se);
}
else{
g2[cnt].pb(id);
min_val2[id].pb(a[cnt].fi - a[cnt].se);
}
return;
}
int mid = (l + r) >> 1;
prep2(id << 1, l, mid, L, R);
prep2(id << 1 | 1, mid + 1, r, L, R);
}
bool cmp(ii a, ii b){
return a.se < b.se;
}
priority_queue<int, vector<int>, greater<int>> pq;
int find_mn1(int id, int value){
int answer = 0;
for(int i = 19; i >= 0; i--){
if((answer + (1LL << i)) >= bit1[id].size()) continue;
if(value > bit1[id][answer + (1LL << i)]){
value -= bit1[id][answer + (1LL << i)];
answer += (1LL << i);
}
}
return answer + 1;
}
int find_mn2(int id, int value){
int answer = 0;
for(int i = 19; i >= 0; i--){
if((answer + (1LL << i)) >= bit2[id].size()) continue;
if(value > bit2[id][answer + (1LL << i)]){
value -= bit2[id][answer + (1LL << i)];
answer += (1LL << i);
}
}
return answer + 1;
}
int pluss;
void gett(int id, int l, int r, int L, int R){
if(l > R || r < L) return;
if(l >= L && r <= R){
if(!type){
int pos = upper_bound(type1[id].begin(), type1[id].end(), val) - type1[id].begin();
pos--;
int tempo = get1(id, pos);
//cout << tempo << "\n";
//return;
for(int i = 1; i <= tempo; i++){
int posi = find_mn1(id, i);
//continue;
// cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
pq.push(type1[id][posi] + pluss);
}
return;
//return get1(id, pos);
}
else{
int pos = upper_bound(type2[id].begin(), type2[id].end(), val) - type2[id].begin();
pos--;
int tempo = get2(id, pos);
//return;
for(int i = 1; i <= tempo; i++){
int posi = find_mn2(id, i);
assert(posi < type2[id].size());
// cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
pq.push(type2[id][posi] + pluss);
}
return;
//return get2(id, pos);
}
}
int mid = (l + r) >> 1;
gett(id << 1, l, mid, L, R);
gett(id << 1 | 1, mid + 1, r, L, R);
}
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
void process(){
cin >> n >> k;
/*
n = k = 100000;
set<ii> se;
while(se.size() < n) se.insert({rnd(-1e9, 1e9), rnd(-1e9, 1e9)});
int cntt = 0;
for(auto it : se){
cntt++;
a[cntt] = it;
}*/
for(int i = 1; i <= n; i++){
cin >> a[i].fi >> a[i].se;
b[i] = a[i];
x.pb(a[i].fi), y.pb(a[i].se);
}
sort(x.begin(), x.end()), sort(y.begin(), y.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
y.resize(unique(y.begin(), y.end()) - y.begin());
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1, cmp);
for(int i = 1; i <= n; i++) mp[b[i]] = i;
build(1, 1, n);
//return;
for(int i = 1; i <= 524288; i++){
type1[i].pb(-oo), type2[i].pb(-oo);
sort(type1[i].begin(), type1[i].end());
sort(type2[i].begin(), type2[i].end());
}
//return;
int l = 1, r = 4e9 + 5;
int itr = 0;
for(int i = 1; i <= n; i++) savee[i] = mp[a[i]];
for(int i = 1; i <= n; i++){
cnt++;
point = a[i];
prep(1, 1, n, savee[i]);
type = 0;
prep2(1, 1, n, 1, savee[i]);
type = 1;
prep2(1, 1, n, savee[i] + 1, n);
}
for(int i = 1; i <= 524288; i++){
//min_val1[i] = oo, min_val2[i] = oo;
reverse(min_val1[i].begin(), min_val1[i].end());
reverse(min_val2[i].begin(), min_val2[i].end());
int mini = oo;
for(int j = 0; j < min_val1[i].size(); j++){
mini = min(mini, min_val1[i][j]);
min_val1[i][j] = mini;
}
mini = oo;
for(int j = 0; j < min_val2[i].size(); j++){
mini = min(mini, min_val2[i][j]);
min_val2[i][j] = mini;
}
}
int tol_size = 0;
for(int i = 1; i <= 524288; i++){
tol_size += min_val1[i].size();
tol_size += min_val2[i].size();
}
//cout << tol_size << "\n";
int cnttt = 0, cnttt2 = 0;
while(l < r){
int mid = (l + r) >> 1;
for(int i = 1; i <= 524288; i++){
for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
mini1[i] = mini2[i] = oo;
min_val3[i].resize(min_val1[i].size());
for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
min_val4[i].resize(min_val2[i].size());
for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];
//min_val4[i] = min_val2[i];
}
int answer = 0, total = 0;
for(int i = 1; i <= n; i++){
int pos = savee[i];
// cout << pos << " ";
val = mid - a[i].fi - a[i].se;
//answer += get(1, 1, n, 1, pos);
for(auto it : g1[i]){
min_val3[it].pop_back();
if(mini1[it] == oo || type1[it][mini1[it]] > val) continue;
cnttt2++;
int pos = upper_bound(type1[it].begin(), type1[it].end(), val) - type1[it].begin();
pos--;
assert(mini1[it] == oo || pos >= mini1[it]);
//cout << i << " " << it << " " << val << " " << pos << " " << mini1[it] << " " << get1(it, pos) << "\n";
//assert(get1(it, pos) > 0);
//cout << "OK " << id << " " << pos << " " << type1[id].size() << "\n";
answer += get1(it, pos);
}
val = mid - a[i].fi + a[i].se;
for(auto it : g2[i]){
min_val4[it].pop_back();
if(mini2[it] == oo || type2[it][mini2[it]] > val) continue;
cnttt2++;
int pos = upper_bound(type2[it].begin(), type2[it].end(), val) - type2[it].begin();
pos--;
//assert(get2(it, pos) > 0);
//cout << "OK " << id << " " << pos << " " << type2[id].size() << "\n";
answer += get2(it, pos);
}
//answer += get(1, 1, n, pos + 1, n);
//continue;
//cout << answer << "\n";
//point = a[i];
if(answer >= k) break;
for(auto it : u1[i]){
if(!min_val3[it.fi].size() || (min_val3[it.fi].back() - a[i].fi - a[i].se) > mid) continue;
total++;
upd1(it.fi, it.se);
mini1[it.fi] = min(mini1[it.fi], it.se);
cnttt++;
}
for(auto it : u2[i]){
if(!min_val4[it.fi].size() || (min_val4[it.fi].back() - a[i].fi + a[i].se) > mid) continue;
total++;
upd2(it.fi, it.se);
mini2[it.fi] = min(mini2[it.fi], it.se);
cnttt++;
}
/*
if(total >= k){
answer = k;
break;
}*/
//upd(1, 1, n, pos);
}
//cout << mid << " " << total << " " << answer << "\n";
//return;
//cout << mid << " " << answer << "\n";
if(answer < k) l = mid + 1;
else r = mid;
// itr++;
//if(itr == 1) return;
}
//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
//cout << cnttt << " " << cnttt2 << "\n";
//return;
//cout << l << "\n";
l--;
for(int i = 1; i <= 524288; i++){
for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
}
for(int i = 1; i <= n; i++){
int pos = mp[a[i]];
type = 0, val = l - a[i].fi - a[i].se, pluss = a[i].fi + a[i].se;
gett(1, 1, n, 1, pos);
type = 1, val = l - a[i].fi + a[i].se, pluss = a[i].fi - a[i].se;
gett(1, 1, n, pos + 1, n);
for(auto it : u1[i]) upd1(it.fi, it.se);
for(auto it : u2[i]) upd2(it.fi, it.se);
//continue;
//point = a[i];
//upd(1, 1, n, pos);
}
l++;
//return;
//cout << pq.size() << '\n';
//assert(pq.size() <= k);
while(pq.size() < k) pq.push(l);
for(int i = 1; i <= k; i++){
int x = pq.top();
pq.pop();
cout << x << "\n";
}
//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("road.inp", "r", stdin);
//freopen("road.out", "w", stdout);
cin.tie(0);
process();
}
Compilation message
road_construction.cpp: In function 'void upd1(long long int, long long int)':
road_construction.cpp:55:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
| ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void upd2(long long int, long long int)':
road_construction.cpp:67:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
| ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn1(long long int, long long int)':
road_construction.cpp:142:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if((answer + (1LL << i)) >= bit1[id].size()) continue;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn2(long long int, long long int)':
road_construction.cpp:154:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | if((answer + (1LL << i)) >= bit2[id].size()) continue;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from road_construction.cpp:1:
road_construction.cpp: In function 'void gett(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:190:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | assert(posi < type2[id].size());
| ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void process()':
road_construction.cpp:257:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
257 | for(int j = 0; j < min_val1[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:262:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
262 | for(int j = 0; j < min_val2[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:277:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
277 | for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
| ~~^~~~~~~~~~~~~~~~
road_construction.cpp:278:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
278 | for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
| ~~^~~~~~~~~~~~~~~~
road_construction.cpp:281:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
281 | for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
| ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:283:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
283 | for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];
| ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:288:8: warning: unused variable 'pos' [-Wunused-variable]
288 | int pos = savee[i];
| ^~~
road_construction.cpp:355:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
355 | for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
| ~~^~~~~~~~~~~~~~~~
road_construction.cpp:356:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
356 | for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
| ~~^~~~~~~~~~~~~~~~
road_construction.cpp:374:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
374 | while(pq.size() < k) pq.push(l);
| ~~~~~~~~~~^~~
road_construction.cpp:241:6: warning: unused variable 'itr' [-Wunused-variable]
241 | int itr = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
169472 KB |
Output is correct |
| 2 |
Correct |
346 ms |
169392 KB |
Output is correct |
| 3 |
Correct |
331 ms |
169088 KB |
Output is correct |
| 4 |
Correct |
332 ms |
169152 KB |
Output is correct |
| 5 |
Correct |
347 ms |
168320 KB |
Output is correct |
| 6 |
Correct |
257 ms |
164680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10124 ms |
773592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9734 ms |
770428 KB |
Output is correct |
| 2 |
Execution timed out |
10109 ms |
775632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9734 ms |
770428 KB |
Output is correct |
| 2 |
Execution timed out |
10109 ms |
775632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
169472 KB |
Output is correct |
| 2 |
Correct |
346 ms |
169392 KB |
Output is correct |
| 3 |
Correct |
331 ms |
169088 KB |
Output is correct |
| 4 |
Correct |
332 ms |
169152 KB |
Output is correct |
| 5 |
Correct |
347 ms |
168320 KB |
Output is correct |
| 6 |
Correct |
257 ms |
164680 KB |
Output is correct |
| 7 |
Correct |
5966 ms |
406028 KB |
Output is correct |
| 8 |
Correct |
5929 ms |
405968 KB |
Output is correct |
| 9 |
Correct |
339 ms |
169120 KB |
Output is correct |
| 10 |
Correct |
4486 ms |
404964 KB |
Output is correct |
| 11 |
Correct |
3770 ms |
404720 KB |
Output is correct |
| 12 |
Correct |
3870 ms |
394356 KB |
Output is correct |
| 13 |
Correct |
4135 ms |
395560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
169472 KB |
Output is correct |
| 2 |
Correct |
346 ms |
169392 KB |
Output is correct |
| 3 |
Correct |
331 ms |
169088 KB |
Output is correct |
| 4 |
Correct |
332 ms |
169152 KB |
Output is correct |
| 5 |
Correct |
347 ms |
168320 KB |
Output is correct |
| 6 |
Correct |
257 ms |
164680 KB |
Output is correct |
| 7 |
Execution timed out |
10124 ms |
773592 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
