Submission #1143492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143492		VMaksimoski008	Road Construction (JOI21_road_construction)	C++20	32 / 100	10093 ms	14412 KiB

road_construction

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 3e5 + 5;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = 
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, K;
bool flag = 0;
ll cnt = 0, mid, need;
vector<ar<int, 2> > a(maxn);
vector<ll> vec;
Tree<pll> st;

bool cmp(ar<int, 2> x, ar<int, 2> y) {
    return x[1] < y[1];
}

void dnc(int l, int r) {
    if(l >= r) return ;

    int tm = (l + r) / 2;
    vector<ar<int, 2> > L, R;
    for(int i=l; i<=tm; i++) L.push_back(a[i]);
    for(int i=tm+1; i<=r; i++) R.push_back(a[i]);
    sort(L.begin(), L.end(), cmp);
    sort(R.begin(), R.end(), cmp);

    st.clear();

    int p = 0;
    for(auto [x, y] : R) {
        while(p < L.size() && L[p][1] < y) {
            st.insert({ - L[p][0] - L[p][1], p });
            p++;
        }

        if(!st.empty() && flag) {
            auto it = st.begin();
            while(it != st.end() && x + y + it->first <= mid) {
                vec.push_back(x + y + it->first);
                it++;
            }
        }

        cnt += st.order_of_key({ mid - (x + y) + 1, 0 });
    }

    st.clear();

    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    p = 0;
    for(auto [x, y] : R) {
        while(p < L.size() && L[p][1] >= y) {
            st.insert({ - L[p][0] + L[p][1], p });
            p++;
        }

        if(!st.empty() && flag) {
            auto it = st.begin();
            while(it != st.end() && x - y + it->first <= mid) {
                vec.push_back(x - y + it->first);
                it++;
            }
        }

        cnt += st.order_of_key({ mid - x + y + 1, 0 });
    }

    dnc(l, tm);
    dnc(tm+1, r);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);


    cin >> n >> K;
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin()+1, a.begin()+n+1);

    ll l=0, r=4e9, ans=4e9;
    while(l <= r) {
        mid = (l + r) / 2;
        cnt = 0;
        need = K;
        vec.clear();
        dnc(1, n);
        if(cnt >= K) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    vec.clear();
    flag = 1;
    mid = ans - 1;
    dnc(1, n);

    while(vec.size() < K) vec.push_back(ans);
    sort(vec.begin(), vec.end());
    for(auto x : vec) cout << x << '\n';
}

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