Submission #876226

#TimeUsernameProblemLanguageResultExecution timeMemory
876226RegulusRoad Construction (JOI21_road_construction)C++17
100 / 100
1852 ms13908 KiB
#include <bits/stdc++.h> // pA #define IO ios::sync_with_stdio(false);cin.tie(0); #define debug(x) cerr << #x << " = " << (x) << ' ' #define endl cerr << '\n' #define all(v) (v).begin(), (v).end() #define SZ(v) (ll)(v).size() #define lowbit(x) (x)&-(x) #define pb emplace_back #define F first #define S second using namespace std; using ll = long long; using pll = pair<ll, ll>; const int N = 3e5+5; const ll INF = 1e18; ll n, Q; pll p[N]; multiset<pll> st; vector<ll> v; //#define test inline bool chk(ll w) { ll i, L=1, x, y; st.clear(), v.clear(); for (i=1; i <= n; ++i) { while (p[i].F-p[L].F > w) { #ifdef test debug(i), debug(L), debug(w), endl; #endif st.erase(st.find({p[L].S, p[L].F})); ++L; } for (auto it = st.lower_bound({p[i].S, -INF}); it != st.end(); ++it) { x = it->S, y = it->F; if (y-p[i].S > w) break; v.pb(max(abs(x-p[i].F), abs(y-p[i].S))); if (SZ(v) >= Q) return 1; } auto it = st.lower_bound({p[i].S, -INF}); if (it != st.begin()) { --it; for ( ; ; --it) { x = it->S, y = it->F; if (p[i].S-y > w) break; v.pb(max(abs(x-p[i].F), abs(y-p[i].S))); if (SZ(v) >= Q) return 1; if (it == st.begin()) break; } } st.insert({p[i].S, p[i].F}); #ifdef test debug(i), endl; for (auto x : st) cerr << x.F << ' ' << x.S << '\n'; #endif } return 0; } int main(void) { IO ll i, lb, mid, ub, x, y; cin >> n >> Q; for (i=1; i <= n; ++i) cin >> x >> y, p[i] = {x+y, x-y}; sort(p+1, p+n+1); #ifndef test lb = 0, ub = 1e18; while (lb < ub) { mid = (lb+ub)>>1; if (chk(mid)) ub = mid; else lb = mid + 1; } chk(lb-1); sort(all(v)); for (i=0; i < min(Q, SZ(v)); ++i) cout << v[i] << '\n'; for (i=0; i < max(Q-SZ(v), 0LL); ++i) cout << lb << '\n'; #else endl; for (i=1; i <= n; ++i) debug(p[i].F), debug(p[i].S), endl; endl; chk(2); endl; for (ll x : v) debug(x), endl; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...