oj.uz

Submission #1080305

# Submission time Handle Problem Language Result Execution time Memory
1080305 2024-08-29T08:44:25 Z CDuong Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 160300 KB 
/*
#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

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();
      |                 ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 18768 KB Output is correct
2 Correct 215 ms 18852 KB Output is correct
3 Correct 194 ms 18768 KB Output is correct
4 Correct 183 ms 18768 KB Output is correct
5 Correct 112 ms 4688 KB Output is correct
6 Correct 8 ms 600 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5429 ms 157080 KB Output is correct
2 Correct 5536 ms 160180 KB Output is correct
3 Correct 156 ms 18772 KB Output is correct
4 Correct 5498 ms 160048 KB Output is correct
5 Correct 5739 ms 160000 KB Output is correct
6 Correct 5733 ms 160300 KB Output is correct
7 Correct 5295 ms 160136 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10013 ms 156976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10013 ms 156976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 18768 KB Output is correct
2 Correct 215 ms 18852 KB Output is correct
3 Correct 194 ms 18768 KB Output is correct
4 Correct 183 ms 18768 KB Output is correct
5 Correct 112 ms 4688 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 6099 ms 61600 KB Output is correct
8 Correct 6239 ms 61504 KB Output is correct
9 Correct 200 ms 18872 KB Output is correct
10 Correct 4905 ms 61360 KB Output is correct
11 Correct 4473 ms 60396 KB Output is correct
12 Correct 2017 ms 31044 KB Output is correct
13 Correct 1951 ms 39276 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 18768 KB Output is correct
2 Correct 215 ms 18852 KB Output is correct
3 Correct 194 ms 18768 KB Output is correct
4 Correct 183 ms 18768 KB Output is correct
5 Correct 112 ms 4688 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 5429 ms 157080 KB Output is correct
8 Correct 5536 ms 160180 KB Output is correct
9 Correct 156 ms 18772 KB Output is correct
10 Correct 5498 ms 160048 KB Output is correct
11 Correct 5739 ms 160000 KB Output is correct
12 Correct 5733 ms 160300 KB Output is correct
13 Correct 5295 ms 160136 KB Output is correct
14 Execution timed out 10013 ms 156976 KB Time limit exceeded
15 Halted 0 ms 0 KB -