oj.uz

Submission #893357

# Submission time Handle Problem Language Result Execution time Memory
893357 2023-12-27T03:10:48 Z vjudge1 Road Construction (JOI21_road_construction) C++17
100 / 100
 9945 ms 131540 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);
    }
};

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

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

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5312 KB Output is correct
2 Correct 50 ms 5320 KB Output is correct
3 Correct 42 ms 5308 KB Output is correct
4 Correct 41 ms 5464 KB Output is correct
5 Correct 48 ms 4120 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 4670 ms 125572 KB Output is correct
2 Correct 4633 ms 128452 KB Output is correct
3 Correct 36 ms 5320 KB Output is correct
4 Correct 4439 ms 128348 KB Output is correct
5 Correct 4221 ms 128640 KB Output is correct
6 Correct 4204 ms 128448 KB Output is correct
7 Correct 4317 ms 127996 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9336 ms 122236 KB Output is correct
2 Correct 9157 ms 122184 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4165 ms 122028 KB Output is correct
5 Correct 3612 ms 122156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9336 ms 122236 KB Output is correct
2 Correct 9157 ms 122184 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4165 ms 122028 KB Output is correct
5 Correct 3612 ms 122156 KB Output is correct
6 Correct 9794 ms 122232 KB Output is correct
7 Correct 9141 ms 122232 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 9418 ms 122272 KB Output is correct
11 Correct 4152 ms 122156 KB Output is correct
12 Correct 3540 ms 122388 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 5320 KB Output is correct
3 Correct 42 ms 5308 KB Output is correct
4 Correct 41 ms 5464 KB Output is correct
5 Correct 48 ms 4120 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 3529 ms 57632 KB Output is correct
8 Correct 3450 ms 57112 KB Output is correct
9 Correct 41 ms 5564 KB Output is correct
10 Correct 3262 ms 56276 KB Output is correct
11 Correct 3106 ms 56256 KB Output is correct
12 Correct 1012 ms 56848 KB Output is correct
13 Correct 1554 ms 55568 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5312 KB Output is correct
2 Correct 50 ms 5320 KB Output is correct
3 Correct 42 ms 5308 KB Output is correct
4 Correct 41 ms 5464 KB Output is correct
5 Correct 48 ms 4120 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 4670 ms 125572 KB Output is correct
8 Correct 4633 ms 128452 KB Output is correct
9 Correct 36 ms 5320 KB Output is correct
10 Correct 4439 ms 128348 KB Output is correct
11 Correct 4221 ms 128640 KB Output is correct
12 Correct 4204 ms 128448 KB Output is correct
13 Correct 4317 ms 127996 KB Output is correct
14 Correct 9336 ms 122236 KB Output is correct
15 Correct 9157 ms 122184 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 4165 ms 122028 KB Output is correct
18 Correct 3612 ms 122156 KB Output is correct
19 Correct 9794 ms 122232 KB Output is correct
20 Correct 9141 ms 122232 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 9418 ms 122272 KB Output is correct
24 Correct 4152 ms 122156 KB Output is correct
25 Correct 3540 ms 122388 KB Output is correct
26 Correct 3529 ms 57632 KB Output is correct
27 Correct 3450 ms 57112 KB Output is correct
28 Correct 41 ms 5564 KB Output is correct
29 Correct 3262 ms 56276 KB Output is correct
30 Correct 3106 ms 56256 KB Output is correct
31 Correct 1012 ms 56848 KB Output is correct
32 Correct 1554 ms 55568 KB Output is correct
33 Correct 9945 ms 131436 KB Output is correct
34 Correct 9832 ms 131168 KB Output is correct
35 Correct 8977 ms 130824 KB Output is correct
36 Correct 3115 ms 131540 KB Output is correct
37 Correct 3198 ms 131168 KB Output is correct
38 Correct 4351 ms 129960 KB Output is correct