oj.uz

답안 #1080287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1080287 2024-08-29T08:38:40 Z CDuong Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 159784 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});
        // 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

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 18796 KB Output is correct
2 Correct 192 ms 18912 KB Output is correct
3 Correct 191 ms 18896 KB Output is correct
4 Correct 212 ms 19028 KB Output is correct
5 Correct 113 ms 4944 KB Output is correct
6 Correct 8 ms 604 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5722 ms 158840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10107 ms 159784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10107 ms 159784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 18796 KB Output is correct
2 Correct 192 ms 18912 KB Output is correct
3 Correct 191 ms 18896 KB Output is correct
4 Correct 212 ms 19028 KB Output is correct
5 Correct 113 ms 4944 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Correct 6445 ms 63556 KB Output is correct
8 Correct 6022 ms 63812 KB Output is correct
9 Correct 189 ms 19024 KB Output is correct
10 Correct 4852 ms 64176 KB Output is correct
11 Correct 4381 ms 62124 KB Output is correct
12 Correct 1922 ms 33608 KB Output is correct
13 Correct 1812 ms 39276 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 18796 KB Output is correct
2 Correct 192 ms 18912 KB Output is correct
3 Correct 191 ms 18896 KB Output is correct
4 Correct 212 ms 19028 KB Output is correct
5 Correct 113 ms 4944 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Incorrect 5722 ms 158840 KB Output isn't correct
8 Halted 0 ms 0 KB -