/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option
#include<bits/stdc++.h>
using namespace std;
#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define eb emplace_back
#define ii pair<int, int>
#define iii pair<int, ii>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 500005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;
int cx[maxN], cy[maxN];
vi ord;
int ftree[maxN];
void inc(int plc){
while(plc < maxN){
++ftree[plc];
plc += plc & -plc;
}
}
int take(int plc){
int res = 0;
while(plc){
res += ftree[plc];
plc -= plc & -plc;
}
return res;
}
int retro(int cut){
int cry = cut + 1;
memset(ftree, 0, sizeof(ftree));
int res = 0;
vector<iii> qry;
for1(i, 1, n){
qry.pb({cy[i], ii(-2, cx[i])});
qry.pb({cy[i] - cry, ii(-1, cx[i] + cut)});
qry.pb({cy[i] - cry, ii(1 , cx[i] - cry)});
qry.pb({cy[i] + cut, ii(1 , cx[i] + cut)});
qry.pb({cy[i] + cut, ii(-1, cx[i] - cry)});
}
sort(all(qry));
for(iii pr : qry){
int cof = pr.se.fi;
int plc = pr.se.se;
plc = upper_bound(all(ord), plc) - ord.begin() - 1;
if(cof == -2) inc(plc);
else res += take(plc) * cof;
}
res -= n;
assert(res % 2 == 0);
return res / 2;
}
signed main(){
freopen(".inp", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
for1(i, 1, n){
cin >> x >> y;
cx[i] = x + y;
cy[i] = x - y;
ord.pb(cx[i]);
}
ord.pb(-oo);
ord.pb(oo);
sort(all(ord)); ord.resize(unique(all(ord)) - ord.begin());
int l = 1, r = mod * 10;
while(l != r){
int mid = (l + r) / 2;
if(retro(mid) >= k) r = mid;
else l = mid + 1;
}
vector<ii> tray;
for1(i, 1, n) tray.pb(ii(cy[i], cx[i]));
sort(all(tray));
for(ii &pr : tray) swap(pr.fi, pr.se);
set<ii> st;
st.insert(ii(oo, oo));
--l;
vi ans;
for(ii pr : tray){
ii coke = {pr.fi - l, -oo};
while(1){
int dt = abs(coke.fi - pr.fi);
int ds = abs(coke.se - pr.se);
if(dt > l) break;
if(ds <= l)
ans.pb(max(ds, abs(coke.fi - pr.fi)));
else st.erase(coke);
coke = *st.upper_bound(coke);
}
st.insert(pr);
}
sort(all(ans));
while(ans.size() < k) ans.pb(r);
for(int cc : ans) cout << cc << endl;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:118: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]
118 | while(ans.size() < k) ans.pb(r);
| ~~~~~~~~~~~^~~
road_construction.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen(".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
