Submission #1080339

#TimeUsernameProblemLanguageResultExecution timeMemory
1080339CDuongRoad Construction (JOI21_road_construction)C++17
100 / 100
5917 ms36016 KiB
/* #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define i64 long long #define int long long #define isz(x) (int)x.size() using namespace std; template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3> struct segment_tree_base{ static_assert(HAS_QUERY || HAS_UPDATE); #define ifQ if constexpr(HAS_QUERY) #define ifU if constexpr(HAS_UPDATE) int n, size, log; vector<T> data; vector<U> data_action; F1 TT; // monoid operation (always adjacent) T T_id; // monoid identity F2 UU; // monoid operation (superset, subset) U U_id; // monoid identity F3 UT; // action of U on T (superset, subset) // O(n) segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ } segment_tree_base &operator=(const segment_tree_base &seg){ n = seg.n; size = seg.size; log = seg.log; data = seg.data; data_action = seg.data_action; } // O(1) friend void swap(segment_tree_base &x, segment_tree_base &y){ swap(x.n, y.n); swap(x.size, y.size); swap(x.log, y.log); swap(x.data, y.data); swap(x.data_action, y.data_action); } // O(n) void build(int n){ assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); ifQ data.assign(size << 1, T_id); ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id); } // O(n) void build(int n, T x){ static_assert(HAS_QUERY); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); fill(data.begin() + size, data.begin() + size + n, x); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) template<class V> void build(const vector<V> &a){ static_assert(HAS_QUERY); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); copy(a.begin(), a.end(), data.begin() + size); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) void build_action(int n){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); build(n); } // O(n) void build_action(int n, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); fill(data_action.begin() + size, data_action.begin() + size + n, f); } // O(n) template<class V> void build_action(const vector<V> &a){ static_assert(!HAS_QUERY && HAS_UPDATE); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); copy(a.begin(), a.end(), data_action.begin() + size); } // O(1) void refresh(int u){ static_assert(HAS_QUERY); data[u] = TT(data[u << 1], data[u << 1 | 1]); } // O(1) void apply(int u, U f){ static_assert(HAS_UPDATE); ifQ data[u] = UT(f, data[u]); if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]); } // O(1) void push(int u){ static_assert(HAS_UPDATE); apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]); data_action[u] = U_id; } // O(log(n)) if HAS_UPDATE, O(1) otherwise. T query(int p){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data[p]; } // O(log(n)) U query_action(int p){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data_action[p]; } // O(log(n)) T query(int ql, int qr){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return T_id; ql += size, qr += size; ifU for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } T res_left = T_id, res_right = T_id; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) res_left = TT(res_left, data[ql ++]); if(qr & 1) res_right = TT(data[-- qr], res_right); } return TT(res_left, res_right); } // O(1) T query_all() const{ static_assert(HAS_QUERY); return data[1]; } // O(n) vector<T> to_array(){ static_assert(HAS_QUERY); ifU for(auto u = 1; u < size; ++ u) push(u); return vector<T>(data.begin() + size, data.begin() + size + n); } // O(n) vector<U> to_array_of_updates(){ static_assert(!HAS_QUERY && HAS_UPDATE); for(auto u = 1; u < size; ++ u) push(u); return vector<U>(data_action.begin() + size, data_action.begin() + size + n); } // O(log(n)) void set(int p, T x){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); data[p] = x; for(auto i = 1; i <= log; ++ i) refresh(p >> i); } // O(log(n)) void set_action(int p, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); data_action[p] = f; } // O(log(n)) void update(int p, U f){ static_assert(HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); ifQ{ data[p] = UT(f, data[p]); for(auto i = 1; i <= log; ++ i) refresh(p >> i); } else data_action[p] = UU(f, data_action[p]); } // O(log(n)) void update(int ql, int qr, U f){ static_assert(HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) apply(ql ++, f); if(qr & 1) apply(-- qr, f); } ql = _ql, qr = _qr; ifQ for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){ static_assert(HAS_QUERY && HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } auto recurse = [&](auto self, int u)->void{ if(exit_rule(data[u])) return; if(enter_rule(data[u])){ apply(u, update_rule(data[u])); return; } push(u); self(self, u << 1), self(self, u << 1 | 1); refresh(u); }; int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) recurse(recurse, ql ++); if(qr & 1) recurse(recurse, -- qr); } ql = _ql, qr = _qr; for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F // Returns max r with T // O(log(n)) int max_pref(int ql, auto pred){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= n && pred(T_id)); if(ql == n) return n; ql += size; ifU for(auto i = log; i >= 1; -- i) push(ql >> i); T sum = T_id; do{ while(~ql & 1) ql >>= 1; if(!pred(TT(sum, data[ql]))){ while(ql < size){ ifU push(ql); ql = ql << 1; if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]); } return ql - size; } sum = TT(sum, data[ql]); ++ ql; }while((ql & -ql) != ql); return n; } // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T // Returns min l with T // O(log(n)) int min_suff(int qr, auto pred){ static_assert(HAS_QUERY); assert(0 <= qr && qr <= n && pred(T_id)); if(qr == 0) return 0; qr += size; ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i); T sum = T_id; do{ -- qr; while(qr > 1 && qr & 1) qr >>= 1; if(!pred(TT(data[qr], sum))){ while(qr < size){ ifU push(qr); qr = qr << 1 | 1; if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum); } return qr + 1 - size; } sum = TT(data[qr], sum); }while((qr & -qr) != qr); return 0; } template<class output_stream> friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){ out << "{"; for(auto i = 0; i < seg.n; ++ i){ ifQ out << seg.query(i); else out << seg.query_action(i); if(i != seg.n - 1) out << ", "; } return out << '}'; } #undef ifQ #undef ifU }; // Supports query template<class T, class F> auto make_Q_segment_tree(F TT, T T_id){ using U = int; auto _UU = [&](U, U)->U{ return U{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT); } // Supports update template<class U, class F> auto make_U_segment_tree(F UU, U U_id){ using T = int; auto _TT = [&](T, T)->T{ return T{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT); } // Supports query and update template<class T, class U, class F1, class F2, class F3> auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){ return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT); } void solve() { int n, k; cin >> n >> k; vector<int> comp_num; vector<pair<int, int>> vec; vector<pair<array<int, 2>, int>> pre_needed; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; vec.emplace_back(x + y, x - y); pre_needed.push_back({{x + y, x - y}, 1}); comp_num.emplace_back(x - y); } sort(all(vec)); sort(all(comp_num)); comp_num.erase(unique(comp_num.begin(), comp_num.end()), comp_num.end()); auto op = [&](int a, int b) -> int { return a + b; }; auto st = make_Q_segment_tree(op, 0); st.build(isz(comp_num)); auto getge = [&](int val) -> int { return lower_bound(all(comp_num), val) - comp_num.begin(); }; auto query = [&](int val) { int res = 0; int ptr = 0, ptr2 = 0; for (int i = 0; i < n; ++i) { while (ptr2 < n and vec[i].first - vec[ptr2].first > val) { int pos = getge(vec[ptr2].second); st.set(pos, st.query(pos) - 1); ++ptr2; } while (ptr < n and vec[ptr].first <= vec[i].first + val) { int pos = getge(vec[ptr].second); st.set(pos, st.query(pos) + 1); ++ptr; } int l = getge(vec[i].second - val); int r = getge(vec[i].second + val + 1); res += st.query(l, r) - 1; } while (ptr2 < n) { int pos = getge(vec[ptr2].second); st.set(pos, st.query(pos) - 1); ++ptr2; } return res / 2; }; int l = 0, r = 4e9; while (l < r) { int mid = (l + r) >> 1; if (query(mid) >= k) r = mid; else l = mid + 1; } auto dis = [&](const auto &A, const auto &B) -> int { return max(abs(A.first - B.second), abs(A.second - B.first)); }; int lim = l - 1; int ptr = 0, ptr2 = 0; map<int, int> mp; set<pair<int, int>> s; for (int i = 0; i < n; ++i) { while (ptr2 < n and vec[i].first - vec[ptr2].first > lim) { auto val = vec[ptr2]; swap(val.first, val.second); s.erase(val); ++ptr2; } while (ptr < n and vec[ptr].first <= vec[i].first + lim) { auto val = vec[ptr]; swap(val.first, val.second); s.insert(val); ++ptr; } for (auto it = s.lower_bound(pair<int, int>{vec[i].second - lim, LLONG_MIN}); it != s.end() and it->first <= vec[i].second + lim; it = next(it)) { mp[dis(vec[i], *it)]++; } } for (auto [val, cnt] : mp) if (val) { assert(cnt % 2 == 0); k -= cnt / 2; for (int i = 0; i < cnt / 2; ++i) cout << val << "\n"; } for (int i = 0; i < k; ++i) cout << l << "\n"; } signed main() { #ifndef CDuongg if(fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; cout << "Check array size pls sir" << endl; #endif }

Compilation message (stderr)

road_construction.cpp:226:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  226 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                       ^~~~
road_construction.cpp:226:55: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  226 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                       ^~~~
road_construction.cpp:226:72: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  226 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                        ^~~~
road_construction.cpp:259:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  259 |     int max_pref(int ql, auto pred){
      |                          ^~~~
road_construction.cpp:284:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  284 |     int min_suff(int qr, auto pred){
      |                          ^~~~
#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...