Submission #1186112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186112		user192837	Road Construction (JOI21_road_construction)	C++17	100 / 100	5377 ms	29812 KiB

road_construction

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int inf = 1e9 + 7;
const ll Binf = 1e18;

struct T {
    vector <ll> t[2];
    vector <ll> fn;
    int n, ql, qr, qi, k, qd, ia;
    ll qx;
    void init(int sz, int kx) {
        n = sz, sz += 5; k = kx;
        t[0].assign(sz << 2, -Binf);
        t[1].assign(sz << 2, -Binf);
    }
    void update(int v, int l, int r) {
        if (l == r)
            return t[qd][v] = qx, void();
        int m = l + r >> 1;
        if (qi <= m)
            update(v << 1, l, m);
        else
            update(v << 1 | 1, m + 1, r);
        t[qd][v] = max(t[qd][v << 1], t[qd][v << 1 | 1]);
    }
    void upd(int i, ll x, ll x2) {
        qi = i, qx = x, qd = 0;
        update(1, 1, n);
        qi = i, qx = x2, qd = 1;
        update(1, 1, n); 
    }
    int get(int v, int l, int r) {
        if (k <= 0 || ql > r || l > qr)
            return 0;
        int m = l + r >> 1;
        if (ql <= l && r <= qr) {
            if (l == r) {
                if (t[qd][v] >= qx) {
                    k--;
                    if (ia)
                        fn.emplace_back(qx - t[qd][v]);
                    return 1;
                }
                return 0;
            }
            int ans = 0;
            if (t[qd][v << 1] >= qx)
                ans += get(v << 1, l, m);
            if (t[qd][v << 1 | 1] >= qx)
                ans += get(v << 1 | 1, m + 1, r);
            return ans;
        }
        return get(v << 1, l, m) + get(v << 1 | 1, m + 1, r);
    }
    int query(int l, int r, ll x, int d, int add) {
        if (l > r)
            return 0;
        ql = l, qr = r, qx = x, qd = d, ia = add;
        return get(1, 1, n);
    } 
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector <ar <ll, 3>> a(n);
    vector <ll> b; b.emplace_back(-inf);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = a[i][1];
        b.emplace_back(a[i][1]);
    }
    sort(all(b));
    for (int i = 0; i < n; i++) {
        a[i][1] = lower_bound(all(b), a[i][1]) - b.begin();
        b[a[i][1]] = b[a[i][1] - 1];
    }
    sort(all(a));
    ll l = -1, r = 1e15;
    while (l + 1 < r) {
        ll m = l + r >> 1;
        T st; st.init(n, k + 5);
        ll res = 0;
        for (auto now : a) {
            res += st.query(1, now[1], now[0] + now[2] - m, 0, 0) + st.query(now[1] + 1, n, now[0] - now[2] - m, 1, 0);
            st.upd(now[1], now[0] + now[2], now[0] - now[2]);
        }
        if (res >= k)
            r = m;
        else
            l = m;
    }
    ll res = 0;
    T st; st.init(n, k + 5);
    for (auto now : a) {
        res += st.query(1, now[1], now[0] + now[2] - (r - 1), 0, 1) + st.query(now[1] + 1, n, now[0] - now[2] - (r - 1), 1, 1);
        st.upd(now[1], now[0] + now[2], now[0] - now[2]);
    }
    sort(all(st.fn));
    for (int i = 0; i < k; i++) {
        if (i >= st.fn.size()) {
            cout << r << '\n';
        } else {
            cout << st.fn[i] + r - 1 << '\n';
        }
    }
}

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