oj.uz

Submission #893349

# Submission time Handle Problem Language Result Execution time Memory
893349 2023-12-27T03:05:43 Z vjudge1 Road Construction (JOI21_road_construction) C++17
59 / 100
 9551 ms 127724 KB 
#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);
    }
};

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_, -1}) - 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

road_construction.cpp:59:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   59 |     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:81: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]
   81 |             while ( it < tmp.size() && tmp[it][0] <= R_ ){
      |                     ~~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:175: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]
  175 |     while ( ans.size() < k ){
      |             ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5312 KB Output is correct
2 Correct 50 ms 5312 KB Output is correct
3 Correct 42 ms 5384 KB Output is correct
4 Correct 40 ms 5312 KB Output is correct
5 Correct 48 ms 4288 KB Output is correct
6 Correct 8 ms 860 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4735 ms 125564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9211 ms 122280 KB Output is correct
2 Correct 9285 ms 127316 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 4218 ms 125012 KB Output is correct
5 Correct 3735 ms 127692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9211 ms 122280 KB Output is correct
2 Correct 9285 ms 127316 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 4218 ms 125012 KB Output is correct
5 Correct 3735 ms 127692 KB Output is correct
6 Correct 9551 ms 127716 KB Output is correct
7 Correct 9157 ms 127316 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 9308 ms 127356 KB Output is correct
11 Correct 4256 ms 125348 KB Output is correct
12 Correct 3583 ms 127724 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5312 KB Output is correct
2 Correct 50 ms 5312 KB Output is correct
3 Correct 42 ms 5384 KB Output is correct
4 Correct 40 ms 5312 KB Output is correct
5 Correct 48 ms 4288 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 3514 ms 57112 KB Output is correct
8 Correct 3429 ms 59192 KB Output is correct
9 Correct 40 ms 5312 KB Output is correct
10 Correct 3274 ms 58520 KB Output is correct
11 Correct 3123 ms 58296 KB Output is correct
12 Correct 997 ms 59088 KB Output is correct
13 Correct 1567 ms 57536 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5312 KB Output is correct
2 Correct 50 ms 5312 KB Output is correct
3 Correct 42 ms 5384 KB Output is correct
4 Correct 40 ms 5312 KB Output is correct
5 Correct 48 ms 4288 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Incorrect 4735 ms 125564 KB Output isn't correct
8 Halted 0 ms 0 KB -