Submission #1080287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080287		CDuong	Road Construction (JOI21_road_construction)	C++17	32 / 100	10107 ms	159784 KiB

road_construction

/*
#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});
        // cout << x + y << " " << x - y << endl;
    }
    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) {
        // cout << i << ": " << vec[i].first << " " << vec[i].second << endl;
        while (ptr2 < n and vec[i].first - vec[ptr2].first > lim) {
            auto val = vec[ptr2];
            // cout << "- " << val.first << " " << val.second << endl;
            swap(val.first, val.second);
            s.erase(val);
            ++ptr2;
        }
        while (ptr < n and vec[ptr].first <= vec[i].first + lim) {
            auto val = vec[ptr];
            // cout << "+ " << val.first << " " << val.second << endl;
            swap(val.first, val.second);
            s.insert(val);
            ++ptr;
        }
        for (auto it = s.lower_bound(pair<int, int>{vec[i].second - lim, -1}); it != s.end() and it->first <= vec[i].second + lim; it = next(it)) {
            // cout << it->second << " " << it->first << endl;
            mp[dis(vec[i], *it)]++;
        }
        // cout << endl;
    }

    for (auto [val, cnt] : mp) if (val) {
        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:107:48:   required from here
road_construction.cpp:38:17: warning: unused variable 'size' [-Wunused-variable]
   38 |             int size = (int)hold0.size();
      |                 ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35