| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1027427 | 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 {
int 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());
}
else
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<<" ";
cout << mnVal<<"\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
*/