| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1027821 | underwaterkillerwhale | Road Construction (JOI21_road_construction) | C++17 | 0 ms | 0 KiB |
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>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e12;
const int BASE = 1337;
struct Coor {
ll x, y;
};
int n, K;
Coor a[N];
namespace sub4 {
struct Data {
ll A, B, x;
// bool operator < (const Data &other) const { return x < other.x; }
};
struct Segment_Tree {
int m;
pair<ll,int> st[N << 2];
void init (int n) {
m = n;
rep (i, 1, n << 2) st[i] = {INF, -1};
}
pair<ll,int> mer(pair<ll,int> A,pair<ll,int> B){ if (A.fs < B.fs) return A; return B;}
void update (int id, int l, int r, int pos, pair<ll,int> val) {
if (l > pos || r < pos) return;
if (l == r) {
if (st[id].fs > val.fs) st[id] = val;
return;
}
int mid = l + r >> 1;
update (id<<1,l,mid,pos,val);
update (id<<1|1,mid+1,r,pos,val);
st[id]=mer(st[id<<1],st[id<<1|1]);
}
pair<ll,int> get (int id,int l,int r, int u,int v) {
if (l>v||r<u) return {INF, -1};
if (l>=u&&r<=v) return st[id];
int mid=l+r>>1;
return mer(get(id<<1,l,mid,u,v), get(id<<1|1,mid+1,r,u,v));
}
void update (int pos,pair<ll,int> val) {
update (1,1,m,pos,val);
}
pair<ll,int> get (int u, int v) {
return get(1,1,m,u,v);
}
}ST1, ST2;
int numY;
vector<int> cY;
bool dd[N];
map<pair<int,int>, bool> ck;
void compress () {
rep (i, 1, n) cY.push_back(a[i].y);
sort (ALL(cY));
cY.resize(numY = unique(ALL(cY)) - cY.begin());
}
ll Dist (int A, int B) {
return abs(a[A].x - a[B].x) + abs(a[A].y - a[B].y);
}
struct cmp {
bool operator () (Data A, Data B) { return A.x < B.x || (A.x == B.x && A.A < B.A) || (A.x == B.x && A.A == B.A && A.B < B.B); }
};
void addtoset (set<Data, cmp> &cur, int town) {
if (dd[town]) return;
rep (i, 1, n) {
if (i == town) continue;
// cout << "add: "<<town<<" "<<i<<" "<<Dist(town, i) <<"\n";
cur.insert({town, i, Dist(town, i)});
}
}
void solution() {
compress();
set<Data, cmp> setA;
rep (k, 1, K) {
pair<int,int> town;
ll mnVal = INF;
ST1.init(numY);
ST2.init(numY);
rep (i, 1, n) {
int pos = lower_bound(ALL(cY), a[i].y) - cY.begin() + 1;
if (dd[i] == 1) {
ST1.update (pos, mp(INF, i));
ST2.update (pos, mp(INF, i));
continue;
}
int B1 = ST1.get (1, pos).se;
int B2 = ST2.get (pos, numY).se;
if (B1 != -1 && !dd[B1] && Dist (i, B1) < mnVal) {
mnVal = Dist(i, B1);
town = {i, B1};
}
if (B2 != -1 && !dd[B2] && Dist (i, B2) < mnVal) {
mnVal = Dist (i, B2);
town = {i, B2};
}
ST1.update (pos, mp(-a[i].x - a[i].y, i));
ST2.update (pos, mp(-a[i].x + a[i].y, i));
}
while (!setA.empty()) {
pair<ll,int> cur = {setA.begin()->A, setA.begin()->B};
if (ck[cur]) {
setA.erase(setA.begin());
continue;
}
if (Dist (cur.fs, cur.se) < mnVal) {
mnVal = Dist (cur.fs, cur.se);
town = cur;
setA.erase(setA.begin());
}
break;
}
addtoset(setA, town.fs);
addtoset(setA, town.se);
dd[town.fs] = dd[town.se] = 1;
ck[town] = 1;
ck[mp(town.se, town.fs)] = 1;
// cout << town.fs<<" "<<town.se<<" "<<Dist(town.fs, town.se)<<" ";
cout << mnVal<<"\n";
}
}
}
namespace sub5 {
int m;
Coor b[N];
vector<ll> cY;
struct fenwick_Tree {
int m;
int fen[N];
void init (int _m) {
m = _m;
rep (i, 1, m) fen[i] = 0;
}
void update (int pos, int val) {
for (; pos <= m; pos += pos &-pos) fen[pos] += val;
}
int get (int pos) {
int res = 0;
for (;pos > 0; pos -= pos & -pos) res += fen[pos];
return res;
}
}fen;
int CPR (int x) {
return lower_bound(ALL(cY), x) - cY.begin() + 1;
}
bool check (int X, int K) {
multiset<pair<ll,int>> S;
rep (i, 1, n) {
b[i].x = {a[i].x - a[i].y};
b[i].y = {a[i].x + a[i].y};
}
sort (b + 1, b + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
cY.clear();
rep (i, 1, n) {
cY.push_back(b[i].y);
cY.push_back(b[i].y - X - 1);
cY.push_back(b[i].y + X);
}
sort (ALL(cY));
cY.resize(m = unique(ALL(cY)) - cY.begin());
fen.init(m);
int ptr = 1;
int res = 0;
rep (i, 1, n) {
while (ptr < i && b[ptr].x < b[i].x - X) {
fen.update(CPR(b[ptr].y), -1);
++ptr;
}
int l1 = CPR(b[i].y - X - 1);
int r1 = CPR(b[i].y + X);
res += fen.get(r1) - fen.get(l1);
// cout << l1 <<" "<<r1 <<"\n";
fen.update(CPR(b[i].y), 1);
}
return res >= K;
}
ll BS (ll L, ll R, int K) {
while (L < R) {
ll mid = L + R >> 1;
if (check(mid, K)) R = mid;
else L = mid + 1;
}
return L;
}
void solution() {
// cout << check(3, 4) <<"\n";
rep (i, 1, K) {
cout << BS(0, 4e9, i) <<"\n";
}
}
}
void solution () {
cin >> n >> K;
rep (i, 1, n) {
cin >> a[i].x >> a[i].y;
}
sort (a + 1, a + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
// rep (i, 1, n) cout <<a[i].x<< ","<<a[i].y<<" ";
// cout<<"\n";
if (K <= 10)
sub4 :: solution();
else
sub5 :: solution();
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/