Submission #1080305

#TimeUsernameProblemLanguageResultExecution timeMemory
1080305CDuongRoad Construction (JOI21_road_construction)C++17
38 / 100
10013 ms160300 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<class B, class T> struct fenwick_tree_2d_sparse_sum{ vector<B> X; vector<vector<array<B, 2>>> Y; vector<vector<T>> data; // O(n * log^2(n)) fenwick_tree_2d_sparse_sum(vector<pair<array<B, 2>, T>> init): X(init.size()){ sort(init.begin(), init.end()); for(auto i = 0; i < (int)init.size(); ++ i) X[i] = init[i].first[0]; sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end()); int n = (int)X.size(); Y.resize(n); data.resize(n); vector<vector<pair<array<B, 2>, T>>> hold(n); for(auto i = 0, x = 0; i < (int)init.size(); ++ i){ auto [pos, val] = init[i]; while(X[x] < pos[0]) ++ x; hold[x].push_back({{pos[1], pos[0]}, val}); } for(auto x = 1; x <= n; ++ x) if(x + (x & -x) <= n){ auto &hold0 = hold[x + (x & -x) - 1]; auto &hold1 = hold[x - 1]; int size = (int)hold0.size(); hold0.insert(hold0.end(), hold1.begin(), hold1.end()); } for(auto x = 0; x < n; ++ x){ auto &Y0 = Y[x]; auto &hold0 = hold[x]; auto &data0 = data[x]; sort(hold0.begin(), hold0.end()); Y0.resize(hold0.size()); for(auto j = 0; j < (int)hold0.size(); ++ j) Y0[j] = hold0[j].first; Y0.erase(unique(Y0.begin(), Y0.end()), Y0.end()); data0.resize(Y0.size()); for(auto j = 0, y = 0; j < (int)hold0.size(); ++ j){ while(Y0[y] < hold0[j].first) ++ y; data0[y] += hold0[j].second; } int m = (int)data0.size(); for(auto y = 1; y <= m; ++ y) if(y + (y & -y) <= m) data0[y + (y & -y) - 1] += data0[y - 1]; } } // O(log^2(n)) void update(B _p, B _q, T x){ int p = lower_bound(X.begin(), X.end(), _p) - X.begin(); assert(p < (int)X.size() && X[p] == _p); for(auto i = p + 1; i <= (int)X.size(); i += i & -i){ auto &Y0 = Y[i - 1]; auto &data0 = data[i - 1]; int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin(); assert(q < (int)Y0.size() && Y0[q][0] == _q && Y0[q][1] == _p); for(auto j = q + 1; j <= (int)data0.size(); j += j & -j) data0[j - 1] += x; } } // O(log^2(n)) T prefix(B _xr, B _yr) const{ int xr = lower_bound(X.begin(), X.end(), _xr) - X.begin(); T res = 0; for(auto i = xr; i > 0; i -= i & -i){ auto &Y0 = Y[i - 1]; auto &data0 = data[i - 1]; int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin(); for(auto j = yr; j > 0; j -= j & -j) res += data0[j - 1]; } return res; } // O(log^2(n)) T query(B _xl, B _xr, B _yl, B _yr) const{ return prefix(_xr, _yr) - prefix(_xl, _yr) - prefix(_xr, _yl) + prefix(_xl, _yl); } // O(log^2(n)) T query(B _x, B _y) const{ return prefix(_x + 1, _y + 1) - prefix(_x + 1, _y) - prefix(_x, _y + 1) + prefix(_x, _y); } }; void solve() { int n, k; cin >> n >> k; 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}); } sort(all(vec)); fenwick_tree_2d_sparse_sum BIT2D(pre_needed); auto query = [&](int val) { int res = 0; for (auto [x, y] : vec) { res += BIT2D.query(x - val, x + val + 1, y - val, y + val + 1) - 1; } 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: In instantiation of 'fenwick_tree_2d_sparse_sum<B, T>::fenwick_tree_2d_sparse_sum(std::vector<std::pair<std::array<B, 2>, T> >) [with B = long long int; T = long long int]':
road_construction.cpp:106:48:   required from here
road_construction.cpp:38:17: warning: unused variable 'size' [-Wunused-variable]
   38 |             int size = (int)hold0.size();
      |                 ^~~~
#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...