oj.uz

Submission #742951

# Submission time Handle Problem Language Result Execution time Memory
742951 2023-05-17T06:49:31 Z GrindMachine Road Construction (JOI21_road_construction) C++17
100 / 100
 9197 ms 203080 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        i++;

        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        i++;

        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        vector<pll> a;
    };

    data neutral = data();

    data merge(data &left, data &right) {
        data curr;

        auto &v1 = left.a, &v2 = right.a, &v3 = curr.a;
        ll n = sz(v1), m = sz(v2);
        ll ptr1 = 0, ptr2 = 0;

        while (ptr1 < n and ptr2 < m) {
            if (v1[ptr1] <= v2[ptr2]) {
                v3.pb(v1[ptr1++]);
            }
            else {
                v3.pb(v2[ptr2++]);
            }
        }

        for (; ptr1 < n; ++ptr1) {
            v3.pb(v1[ptr1]);
        }

        for (; ptr2 < m; ++ptr2) {
            v3.pb(v2[ptr2]);
        }

        return curr;
    }

    void create(int i, T v) {
        tr[i].a = v;
    }

    void modify(int i, T v) {

    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    vector<pll> query(int l, int r, ll mn, ll mx) {
        pll px = {mn, -inf2};
        vector<pll> res;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                auto &v = tr[l++].a;
                auto it = upper_bound(all(v), px);
                for (; it != v.end() and it->first <= mx; ++it) {
                    res.pb(*it);
                }
            }

            if (!(r & 1)) {
                auto &v = tr[r--].a;
                auto it = upper_bound(all(v), px);
                for (; it != v.end() and it->first <= mx; ++it) {
                    res.pb(*it);
                }
            }
        }

        return res;
    }
};

void solve(int test_case)
{
    ll n, k; cin >> n >> k;
    vector<pll> a(n);
    rep(i, n) cin >> a[i].ff >> a[i].ss;

    rep(i, n) {
        auto [x, y] = a[i];
        a[i] = {x + y, x - y};
    }

    vector<ll> b;
    rep(i, n) b.pb(a[i].ss);

    sort(all(b));
    b.resize(unique(all(b)) - b.begin());
    ll siz = sz(b);

    vector<array<ll, 3>> inds(n);

    auto get_cnt = [&](ll m) {
        rep(i, n) {
            auto [x, y] = a[i];
            inds[i][0] = lower_bound(all(b), y - m) - b.begin();
            inds[i][1] = lower_bound(all(b), y) - b.begin();
            inds[i][2] = upper_bound(all(b), y + m) - b.begin() - 1;
        }

        vector<array<ll, 3>> events;

        rep(i, n) {
            auto [x, y] = a[i];
            events.pb({x, 0, i});
        }

        rep(i, n) {
            auto [x, y] = a[i];
            events.pb({x - m - 1, 1, i});
            events.pb({x + m, 2, i});
        }

        sort(all(events));
        fenwick<ll> fenw(siz + 5);
        ll res = 0;

        for (auto [x, t, i] : events) {
            if (t == 0) {
                fenw.pupd(inds[i][1], 1);
            }
            else {
                ll c = 1;
                if (t == 1) c = -1;
                ll lx = inds[i][0], rx = inds[i][2];
                res += fenw.query(lx, rx) * c;
            }
        }

        res -= n;
        res /= 2;

        return res;
    };

    ll l = 0, r = 5e9;
    ll mx_cost = inf2;

    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (get_cnt(mid) <= k) {
            mx_cost = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    b.clear();
    rep(i, n) {
        auto [x, y] = a[i];
        b.pb(x - mx_cost), b.pb(x), b.pb(x + mx_cost);
    }

    sort(all(b));
    b.resize(unique(all(b)) - b.begin());
    siz = sz(b);

    vector<vector<pll>> here(siz);
    rep(i, n) {
        auto [x, y] = a[i];
        ll ind = lower_bound(all(b), x) - b.begin();
        here[ind].pb({y, x});
    }

    rep(i, siz) sort(all(here[i]));

    segtree<vector<pll>> st(siz + 5);
    st.build(here, siz);

    vector<ll> ans;

    rep(i, n) {
        auto [x, y] = a[i];
        ll lx = lower_bound(all(b), x - mx_cost) - b.begin();
        ll rx = lower_bound(all(b), x + mx_cost) - b.begin();
        ll mny = y - mx_cost;
        ll mxy = y + mx_cost;

        auto v = st.query(lx, rx, mny, mxy);

        for (auto [y2, x2] : v) {
            if (x == x2 and y == y2) conts;
            ll cost = max(abs(x - x2), abs(y - y2));
            ans.pb(cost);
        }
    }

    sort(all(ans));

    vector<ll> ans2;
    for (int i = 0; i < sz(ans); i += 2) {
        assert(ans[i] == ans[i + 1]);
        ans2.pb(ans[i]);
    }

    ans = ans2;
    while (sz(ans) < k) ans.pb(mx_cost + 1);

    trav(x, ans) cout << x << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

road_construction.cpp: In function 'void solve(int)':
road_construction.cpp:337:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  337 |     for (int i = 0; i < sz(ans); i += 2) {
      |                       ^
road_construction.cpp:343:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  343 |     while (sz(ans) < k) ans.pb(mx_cost + 1);
      |                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11400 KB Output is correct
2 Correct 81 ms 11460 KB Output is correct
3 Correct 73 ms 11312 KB Output is correct
4 Correct 67 ms 11292 KB Output is correct
5 Correct 73 ms 10344 KB Output is correct
6 Correct 16 ms 576 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8020 ms 198352 KB Output is correct
2 Correct 8004 ms 201716 KB Output is correct
3 Correct 69 ms 11200 KB Output is correct
4 Correct 7658 ms 202936 KB Output is correct
5 Correct 7772 ms 202892 KB Output is correct
6 Correct 7947 ms 203080 KB Output is correct
7 Correct 7526 ms 200256 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8447 ms 190956 KB Output is correct
2 Correct 8201 ms 196756 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7727 ms 195724 KB Output is correct
5 Correct 6560 ms 87280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8447 ms 190956 KB Output is correct
2 Correct 8201 ms 196756 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7727 ms 195724 KB Output is correct
5 Correct 6560 ms 87280 KB Output is correct
6 Correct 8955 ms 195948 KB Output is correct
7 Correct 8830 ms 195880 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 8760 ms 187560 KB Output is correct
11 Correct 7692 ms 195740 KB Output is correct
12 Correct 6203 ms 87548 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11400 KB Output is correct
2 Correct 81 ms 11460 KB Output is correct
3 Correct 73 ms 11312 KB Output is correct
4 Correct 67 ms 11292 KB Output is correct
5 Correct 73 ms 10344 KB Output is correct
6 Correct 16 ms 576 KB Output is correct
7 Correct 3412 ms 85104 KB Output is correct
8 Correct 3243 ms 85524 KB Output is correct
9 Correct 69 ms 11292 KB Output is correct
10 Correct 3047 ms 79348 KB Output is correct
11 Correct 2880 ms 76884 KB Output is correct
12 Correct 2333 ms 37000 KB Output is correct
13 Correct 2400 ms 42292 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11400 KB Output is correct
2 Correct 81 ms 11460 KB Output is correct
3 Correct 73 ms 11312 KB Output is correct
4 Correct 67 ms 11292 KB Output is correct
5 Correct 73 ms 10344 KB Output is correct
6 Correct 16 ms 576 KB Output is correct
7 Correct 8020 ms 198352 KB Output is correct
8 Correct 8004 ms 201716 KB Output is correct
9 Correct 69 ms 11200 KB Output is correct
10 Correct 7658 ms 202936 KB Output is correct
11 Correct 7772 ms 202892 KB Output is correct
12 Correct 7947 ms 203080 KB Output is correct
13 Correct 7526 ms 200256 KB Output is correct
14 Correct 8447 ms 190956 KB Output is correct
15 Correct 8201 ms 196756 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 7727 ms 195724 KB Output is correct
18 Correct 6560 ms 87280 KB Output is correct
19 Correct 8955 ms 195948 KB Output is correct
20 Correct 8830 ms 195880 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 320 KB Output is correct
23 Correct 8760 ms 187560 KB Output is correct
24 Correct 7692 ms 195740 KB Output is correct
25 Correct 6203 ms 87548 KB Output is correct
26 Correct 3412 ms 85104 KB Output is correct
27 Correct 3243 ms 85524 KB Output is correct
28 Correct 69 ms 11292 KB Output is correct
29 Correct 3047 ms 79348 KB Output is correct
30 Correct 2880 ms 76884 KB Output is correct
31 Correct 2333 ms 37000 KB Output is correct
32 Correct 2400 ms 42292 KB Output is correct
33 Correct 8933 ms 202712 KB Output is correct
34 Correct 9197 ms 202820 KB Output is correct
35 Correct 8310 ms 178936 KB Output is correct
36 Correct 6116 ms 78572 KB Output is correct
37 Correct 6479 ms 78592 KB Output is correct
38 Correct 6860 ms 92516 KB Output is correct