Submission #386553

#	Time	Username	Problem	Language	Result	Execution time	Memory
386553		PurpleCrayon	Road Construction (JOI21_road_construction)	C++17	100 / 100	9453 ms	35820 KiB

road_construction

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

#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int MAXN = 2.5e5+10;

struct FT {
    int n, bit[MAXN];
    void init(int _n){ n = _n+1; memset(bit, 0, sizeof(bit)); }
    int qry(int idx) { int ret = 0; for (++idx; idx > 0; idx -= idx & -idx) ret += bit[idx]; return ret; }
    int qry(int l, int r) { return qry(r) - qry(l - 1); }
    void upd(int idx, int delta) { for (++idx; idx < n; idx += idx & -idx) bit[idx] += delta; }
} ft;

string to_str(ar<ll, 2> a){ return "(" + to_string(a[0]) + ", " + to_string(a[1]) + ")"; }

ll dist(ar<ll, 2> a, ar<ll, 2> b){
    return abs<ll>(a[0]-b[0]) + abs<ll>(a[1]-b[1]);
}

int n, k;
ar<ll, 2> a[MAXN], oa[MAXN];
ar<ll, 3> b[MAXN];
int cmp[MAXN];
map<ll, int> mp;

int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1], b[i][0] = a[i][0]+a[i][1], b[i][1] = a[i][0]-a[i][1], b[i][2] = i;
        oa[i] = a[i];
    }

    sort(a, a+n), sort(b, b+n);

    for (int i = 0; i < n; i++) mp[b[i][1]]++;
    int cc=0;
    for (auto& it : mp) it.second=cc++;
    for (int i = 0; i < n; i++) cmp[i] = mp[b[i][1]];

    auto cnt = [&](ll x) -> ll { //rotate 90 degrees, now want to find the point in some square
        ft.init(n);
        
        ll ans=0;
        for (int i=0, j=i; i < n; i++){
            for (; j < n && b[j][0]-b[i][0] <= x; j++) 
                ft.upd(cmp[j], 1);

            const ll cl = b[i][1]-x, cr = b[i][1]+x;
    
            auto rit = mp.upper_bound(cr);
            if (rit != mp.begin()){
                rit = prev(rit);

                auto lit = mp.lower_bound(cl);
                if (lit != mp.end()){
                    ans += ft.qry(lit->second, rit->second);
                }
            }
            if (ans-(i+1) >= k) return ans-(i+1);
            ft.upd(cmp[i], -1);
        }
        return ans-n;
    };

    ll lo=-1, hi=1e18+10, mid=(lo+hi)/2;
    while (lo < mid && mid < hi) {
        if (cnt(mid) >= k) hi = mid;
        else lo = mid;
        mid = (lo+hi)/2;
    }

    vector<ll> ans{hi}; ans.reserve(k);
    
    set<pair<ll, int>> s;
    ll x=hi-1;
    for (int i=0, j=i; i < n; i++){
        assert(j >= i);
        for (; j < n && b[j][0]-b[i][0] <= x; j++) 
            s.insert({b[j][1], j});
        s.erase(s.find({b[i][1], i}));

        ll cl = b[i][1]-x, cr = b[i][1]+x;

        auto lit = s.lower_bound({cl, -1});
        while (lit != s.end() && lit->first <= cr) {
            int cv = lit->second;
            ll d = dist(oa[b[i][2]], oa[b[cv][2]]);

            //cerr << i << ' ' << cv << ' ' << to_str(b[i]) << ' ' << to_str(b[cv]) << endl;
            ans.push_back(d);
            lit = next(lit);
        }
    }

    sort(ans.begin(), ans.end());
    while (sz(ans) < k) ans.push_back(ans.back());

    for (auto& it : ans) cout << it << '\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