Submission #893357

#	Time	Username	Problem	Language	Result	Execution time	Memory
893357		vjudge1	Road Construction (JOI21_road_construction)	C++17	100 / 100	9945 ms	131540 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Fenw{
    vector <int> fenw;
    int n;
    Fenw(int n) : fenw(n + 1, 0), n(n) {}
    void upd(int i, int val){
        for (; i <= n; i += i & -i ){
            fenw[i] += val;
        }
    }
    int get(int i){
        int cnt = 0;
        for (; i > 0; i -= i & -i ){
            cnt += fenw[i];
        }
        return cnt;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

const int inf = 1e16;

vector <int> ans;

int X, Y, L_, R_;

struct SegTree{
    vector <vector<ar<int,2>>> T;
    int n;
    SegTree(auto &a){
        n = a.size();
        T.resize(n * 4 + 1);
        auto build = [&](auto build, int v, int l, int r) -> void{
            if ( l == r ){
                T[v].pb(a[l]);
            } else{
                int md = (l + r) >> 1;
                build(build, v * 2, l, md);
                build(build, v * 2 + 1, md + 1, r);
                merge(all(T[v * 2]), all(T[v * 2 + 1]), back_inserter(T[v]));
            }
        };
        build(build, 1, 0, n - 1);
    }
    void query(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return;
        }
        if ( tl <= l && tr >= r ){
            auto &tmp = T[v];
            int it = lower_bound(all(tmp), ar<int,2>{L_, -inf}) - tmp.begin();
            while ( it < tmp.size() && tmp[it][0] <= R_ ){
                ans.pb(max(X - tmp[it][1], abs(tmp[it][0] - Y)));
                it++;
            } return;
        }
        int md = (l + r) >> 1;
        query(v * 2, l, md, tl, tr);
        query(v * 2 + 1, md + 1, r, tl, tr);
    }
    void query(int X_, int Y_, int L, int R, int l, int r){
        if ( l > r ) return;
        X = X_, Y = Y_, L_ = L, R_ = R;
        query(1, 0, n - 1, l, r);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    vector <int> x(n), y(n);
    for ( int i = 0; i < n; i++ ){
        int a, b; cin >> a >> b;
        x[i] = a + b;
        y[i] = a - b;
    }
    { //  just sorting
        vector <int> pp(n);
        iota(all(pp), 0);
        sort(all(pp), [&](int &u, int &v){
            if ( x[u] == x[v] ){
                return y[u] < y[v];
             }
            return x[u] < x[v];
        });
        auto xx_ = x, yy_ = y;
        for ( int i = 0; i < n; i++ ){
            x[i] = xx_[pp[i]];
            y[i] = yy_[pp[i]];
        }
    }
    vector <int> L(n);
    auto ok = [&](int d){
        vector <int> p_;
        int j = 0;
        for ( int i = 0; i < n; i++ ){
            while ( x[i] - x[j] > d ) j++;
            L[i] = j;
            p_.pb(y[i]);
            p_.pb(y[i] - d);
            p_.pb(y[i] + d);
        }
        sort(all(p_));
        p_.resize(unique(all(p_)) - p_.begin());
        int s = p_.size();
        auto get = [&](int x){
            return lower_bound(all(p_), x) - p_.begin() + 1;
        };
        vector <vector<ar<int,3>>> qu(n);
        for ( int i = 1; i < n; i++ ){
            qu[i - 1].pb({1, get(y[i] - d), get(y[i] + d)});
            if ( L[i] > 0 ){
                qu[L[i] - 1].pb({0, get(y[i] - d), get(y[i] + d)});
            }
        }
        int ans = 0;
        Fenw fn(s);
        for ( int i = 0; i < n; i++ ){
            fn.upd(get(y[i]), 1);
            for ( auto &[t, l, r]: qu[i] ){
                if ( t > 0 ){
                    ans += fn.get(l, r);
                } else{
                    ans -= fn.get(l, r);
                }
            }
        }
        return ans < k;
    };
    int l = 0, r = 1e10 + 5;
    while ( l + 1 < r ){
        int md = (l + r) >> 1;
        if ( ok(md) ) l = md;
        else r = md;
    } ok(l);
    vector <ar<int,2>> p(n);
    for ( int i = 0; i < n; i++ ){
        p[i] = {y[i], x[i]};
    }
    SegTree seg(p);
    for ( int i = 0; i < n; i++ ){
        seg.query(x[i], y[i], y[i] - l, y[i] + l, L[i], i - 1);
    }
    while ( ans.size() < k ){
        ans.pb(l + 1);
    }
    sort(all(ans));
    for ( auto &x: ans ){
        cout << x << ln;
    }

    cout << '\n';
}

Compilation message (stderr)

road_construction.cpp:61:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   61 |     SegTree(auto &a){
      |             ^~~~
road_construction.cpp: In member function 'void SegTree::query(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:83:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             while ( it < tmp.size() && tmp[it][0] <= R_ ){
      |                     ~~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:177:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  177 |     while ( ans.size() < k ){
      |             ~~~~~~~~~~~^~~

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