Submission #1266670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266670		nguyn	Road Construction (JOI21_road_construction)	C++17	100 / 100	2630 ms	15296 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>

const int N = 2.5e5 + 5;
const int inf = 2e9 + 100;
int n, k;
pair<ll, ll> a[N];
vector<int> compressed;
int bit[N];
int b[N];
pair<ll, ll> p[N];

void update(int id, int val) {
    for (int i = id; i <= compressed.size(); i += (i & -i)) bit[i] += val;
}

int get(int id) {
    int res = 0;
    for (int i = id; i >= 1; i -= (i & -i)) res += bit[i];
    return res;
}

bool check(ll mid) {
    for (int i = 1; i <= compressed.size(); i++) {
        bit[i] = 0;
    }
    ll res = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        while(a[i].F - a[j].F > mid) {
            update(b[j], -1);
            j++;
        }
        int right = upper_bound(compressed.begin(), compressed.end(), a[i].S + mid) - compressed.begin() - 1;
        int left = lower_bound(compressed.begin(), compressed.end(), a[i].S - mid) - compressed.begin() - 1;
        res += get(right) - get(left);
        update(b[i], 1);
    }
    // cout << res;
    return res >= k;
}

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

    cin >> n >> k;
    compressed.pb(-inf);
    for (int i = 1; i <= n; i++) {
        cin >> p[i].F >> p[i].S;
        a[i].F = p[i].F + p[i].S;
        a[i].S = p[i].F - p[i].S;
        compressed.pb(a[i].S);
    }
    sort(a + 1, a + 1 + n);
    sort(compressed.begin(), compressed.end());
    compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());
    for (int i = 1; i <= n; i++) {
        b[i] = lower_bound(compressed.begin(), compressed.end(), a[i].S) - compressed.begin();
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << a[i].F << " " << a[i].S << " " << b[i] << endl;
    // }
    // check(1);
    ll l = 1;
    ll ans = 1e15;
    ll r = 1e15;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    int j = 1;
    multiset<pair<ll, int>> st;
    vector<ll> res;
    res.pb(ans);
    if (ans != 1) {
        for (int i = 1; i <= n; i++) {
            while(j < i && a[i].F - a[j].F >= ans) {
    //            update(b[j], -1);
                st.erase(st.find({a[j].S, j}));
                j++;
            }
            auto rig = st.lower_bound({a[i].S + ans, 0});
            auto lef = st.upper_bound({a[i].S - ans, n + 1});
            while(lef != st.end() && lef != rig) {
                int id = (*lef).S;
                if (max(a[i].F - a[id].F, abs(a[i].S - a[id].S)) >= ans) break;
                res.pb(max(a[i].F - a[id].F, abs(a[i].S - a[id].S)));
                lef++;
            }
            st.insert({a[i].S, i});
        }
    }
    sort(res.begin(), res.end());
    while(res.size() < k) res.pb(ans);
    for (auto x : res) cout << x << '\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