#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);
}
void addtoset (set<array<ll, 3>> &cur, int town) {
if (dd[town]) return;
rep (i, 1, n) {
if (i == town) continue;
cur.insert({ Dist(town, i), town, i});
}
}
void solution() {
compress();
set<array<ll, 3>> 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()) {
array<ll, 3> curA = *setA.begin();
pair<ll,int> cur = {curA[1], curA[2]};
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] = ck[mp(town.se, town.fs)] = 1;
cout << mnVal<<"\n";
}
}
}
namespace sub5 {
}
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; });
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
*/
Compilation message
road_construction.cpp: In member function 'void sub4::Segment_Tree::update(int, int, int, int, std::pair<long long int, int>)':
road_construction.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In member function 'std::pair<long long int, int> sub4::Segment_Tree::get(int, int, int, int, int)':
road_construction.cpp:61:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
37976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
41796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
573 ms |
74112 KB |
Output is correct |
| 2 |
Correct |
582 ms |
74036 KB |
Output is correct |
| 3 |
Correct |
17 ms |
37980 KB |
Output is correct |
| 4 |
Correct |
153 ms |
74188 KB |
Output is correct |
| 5 |
Correct |
348 ms |
74184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
573 ms |
74112 KB |
Output is correct |
| 2 |
Correct |
582 ms |
74036 KB |
Output is correct |
| 3 |
Correct |
17 ms |
37980 KB |
Output is correct |
| 4 |
Correct |
153 ms |
74188 KB |
Output is correct |
| 5 |
Correct |
348 ms |
74184 KB |
Output is correct |
| 6 |
Correct |
9101 ms |
355912 KB |
Output is correct |
| 7 |
Correct |
8283 ms |
355904 KB |
Output is correct |
| 8 |
Correct |
15 ms |
37980 KB |
Output is correct |
| 9 |
Correct |
15 ms |
38024 KB |
Output is correct |
| 10 |
Correct |
5150 ms |
230592 KB |
Output is correct |
| 11 |
Correct |
1145 ms |
355788 KB |
Output is correct |
| 12 |
Correct |
4373 ms |
324552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
37976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
37976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
