oj.uz

Submission #743091

# Submission time Handle Problem Language Result Execution time Memory
743091 2023-05-17T07:52:55 Z GrindMachine Road Construction (JOI21_road_construction) C++17
100 / 100
 8980 ms 203148 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

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-773554

initially solved without referring to the solution
then tried to optimize by reading some solutions (like the comment mentioned above)

*/

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 ok = [&](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;
            }

            if ((res - n) / 2 >= k) return false;
        }

        return true;
    };

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

    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (ok(mid)) {
            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:340:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  340 |     for (int i = 0; i < sz(ans); i += 2) {
      |                       ^
road_construction.cpp:346: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]
  346 |     while (sz(ans) < k) ans.pb(mx_cost + 1);
      |                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11424 KB Output is correct
2 Correct 81 ms 11440 KB Output is correct
3 Correct 76 ms 11288 KB Output is correct
4 Correct 70 ms 11280 KB Output is correct
5 Correct 84 ms 10332 KB Output is correct
6 Correct 16 ms 588 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8298 ms 201360 KB Output is correct
2 Correct 7644 ms 201676 KB Output is correct
3 Correct 72 ms 11176 KB Output is correct
4 Correct 7553 ms 203148 KB Output is correct
5 Correct 8183 ms 202944 KB Output is correct
6 Correct 8044 ms 203020 KB Output is correct
7 Correct 7614 ms 200188 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8498 ms 196924 KB Output is correct
2 Correct 8237 ms 196728 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7396 ms 195756 KB Output is correct
5 Correct 6154 ms 87276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8498 ms 196924 KB Output is correct
2 Correct 8237 ms 196728 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7396 ms 195756 KB Output is correct
5 Correct 6154 ms 87276 KB Output is correct
6 Correct 8340 ms 195940 KB Output is correct
7 Correct 8530 ms 196252 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 8409 ms 188048 KB Output is correct
11 Correct 7286 ms 195852 KB Output is correct
12 Correct 6094 ms 87624 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11424 KB Output is correct
2 Correct 81 ms 11440 KB Output is correct
3 Correct 76 ms 11288 KB Output is correct
4 Correct 70 ms 11280 KB Output is correct
5 Correct 84 ms 10332 KB Output is correct
6 Correct 16 ms 588 KB Output is correct
7 Correct 3216 ms 85268 KB Output is correct
8 Correct 3254 ms 85436 KB Output is correct
9 Correct 71 ms 11280 KB Output is correct
10 Correct 3078 ms 79204 KB Output is correct
11 Correct 2843 ms 76936 KB Output is correct
12 Correct 2402 ms 37188 KB Output is correct
13 Correct 2418 ms 42208 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11424 KB Output is correct
2 Correct 81 ms 11440 KB Output is correct
3 Correct 76 ms 11288 KB Output is correct
4 Correct 70 ms 11280 KB Output is correct
5 Correct 84 ms 10332 KB Output is correct
6 Correct 16 ms 588 KB Output is correct
7 Correct 8298 ms 201360 KB Output is correct
8 Correct 7644 ms 201676 KB Output is correct
9 Correct 72 ms 11176 KB Output is correct
10 Correct 7553 ms 203148 KB Output is correct
11 Correct 8183 ms 202944 KB Output is correct
12 Correct 8044 ms 203020 KB Output is correct
13 Correct 7614 ms 200188 KB Output is correct
14 Correct 8498 ms 196924 KB Output is correct
15 Correct 8237 ms 196728 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 7396 ms 195756 KB Output is correct
18 Correct 6154 ms 87276 KB Output is correct
19 Correct 8340 ms 195940 KB Output is correct
20 Correct 8530 ms 196252 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 8409 ms 188048 KB Output is correct
24 Correct 7286 ms 195852 KB Output is correct
25 Correct 6094 ms 87624 KB Output is correct
26 Correct 3216 ms 85268 KB Output is correct
27 Correct 3254 ms 85436 KB Output is correct
28 Correct 71 ms 11280 KB Output is correct
29 Correct 3078 ms 79204 KB Output is correct
30 Correct 2843 ms 76936 KB Output is correct
31 Correct 2402 ms 37188 KB Output is correct
32 Correct 2418 ms 42208 KB Output is correct
33 Correct 8980 ms 202412 KB Output is correct
34 Correct 8974 ms 202520 KB Output is correct
35 Correct 8596 ms 178840 KB Output is correct
36 Correct 6069 ms 78608 KB Output is correct
37 Correct 6388 ms 78656 KB Output is correct
38 Correct 6292 ms 92460 KB Output is correct