Submission #1186069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186069		Gray	Road Construction (JOI21_road_construction)	C++20	5 / 100	10095 ms	525688 KiB

road_construction

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct Fenwick{
    vector<unordered_map<ll, ll>> tr;
    ll offs, n;
    Fenwick(ll N){
        n=N+20; offs=10; tr.resize(n+1);
    }
    void add(ll _i, ll _j, ll x){
        // cout << "ADD " << _i << " " << _j << " + " << x << ln;
        _i+=offs; _j+=offs;
        for (ll i=_i; i<=n; i+=(-i&i)){
            for (ll j=_j; j<=n; j+=(-j&j)){
                tr[i][j]+=x;
            }
        }
    }
    ll get(ll _i, ll _j){
        // cout << "GET " << _i << " " << _j << " -> ";
        ll sum=0; _i+=offs; _j+=offs;
        for (ll i=_i; i; i-=(-i&i)){
            for (ll j=_j; j; j-=(-j&j)){
                if (tr[i].count(j)){
                    sum+=tr[i][j];
                }
            }
        }
        // cout << sum << ln;
        return sum;
    }
};

struct FenwickSick{
    unordered_map<ll, multiset<ll>> tr;
    ll n, offs;
    FenwickSick(ll N){
        n=N*4+20; offs=N*2+10;
    }
    void add(ll i, ll x){
        i+=offs; for (; i<=n; i+=(-i&i)){
            tr[i].insert(x);
        }
    }
    void collect(ll i, ll lim, vector<ll> &col){
        i+=offs; for (; i; i-=(-i&i)){
            if (tr[i].empty()) continue;
            auto iter = tr[i].upper_bound(lim);
            if (iter!=tr[i].begin()){
                do{
                    iter--;
                    col.push_back(*iter);
                }while (iter!=tr[i].begin());
            }
        }
    }
};

void solve(){
    ll n, k; cin >> n >> k;
    vector<pair<ll, ll>> pts(n);
    vector<pair<ll, ll>> dpts(n);
    vector<ll> dxs, dys;
    for (ll i=0; i<n; i++){
        cin >> pts[i].ff >> pts[i].ss;
        dpts[i] = {pts[i].ff+pts[i].ss, pts[i].ff-pts[i].ss};
        dxs.push_back(dpts[i].ff); dys.push_back(dpts[i].ss);
    }
    sort(dxs.begin(), dxs.end()); dxs.erase(unique(dxs.begin(), dxs.end()), dxs.end());
    sort(dys.begin(), dys.end()); dys.erase(unique(dys.begin(), dys.end()), dys.end());
    Fenwick tr(max(dys.size(), dxs.size()));
    for (ll i=0; i<n; i++){
        ll indx = lower_bound(dxs.begin(), dxs.end(), dpts[i].ff)-dxs.begin();
        ll indy = lower_bound(dys.begin(), dys.end(), dpts[i].ss)-dys.begin();
        assert(dxs[indx]==dpts[i].ff and dys[indy]==dpts[i].ss);
        tr.add(indx, indy, 1);
    }
    ll l=0, r=1e10, dcnt=0;
    while(l+1<r){
        ll mid = (l+r)/2, cnt=0;
        for (ll i=0; i<n; i++){
            ll fi = dpts[i].ff-mid, fj=dpts[i].ss-mid, ti = dpts[i].ff+mid, tj = dpts[i].ss+mid;
            ll fiid = lower_bound(dxs.begin(), dxs.end(), fi)-dxs.begin()-1;
            ll fjid = lower_bound(dys.begin(), dys.end(), fj)-dys.begin()-1;
            ll tiid = upper_bound(dxs.begin(), dxs.end(), ti)-1-dxs.begin();
            ll tjid = upper_bound(dys.begin(), dys.end(), tj)-1-dys.begin();
            if (fiid<=tiid and fjid<=tjid) {
                cnt+=tr.get(tiid, tjid)-tr.get(tiid, fjid)-tr.get(fiid, tjid)+tr.get(fiid, fjid)-1;
                // cout << i << ": " << tr.get(tiid, tjid)-tr.get(tiid, fjid)-tr.get(fiid, tjid)+tr.get(fiid, fjid) << " ~~ ";
                // cout << fiid << "," << fjid << " <-> " << tiid << "," << tjid << ln;
            }
        }
        // cout <<"At " << mid << " -> " << cnt/2 << ln;
        if (cnt/2<=k) {
            l=mid; dcnt=cnt/2;
        } else r=mid;
    }
    // cout << l << " " << dcnt << ln;
    // return;
    vector<ll> res;
    for (ll i=dcnt; i<k; i++) res.push_back(l+1);
    // for (ll i=0; i<n; i++){
    //     for (ll j=i+1; j<n; j++){
    //         if (abs(pts[i].ff-pts[j].ff)+abs(pts[i].ss-pts[j].ss)<=l) {
    //             res.push_back(abs(pts[i].ff-pts[j].ff)+abs(pts[i].ss-pts[j].ss));
    //         }
    //     }
    // }
    // sort(res.begin(), res.end());
    // for (auto ch:res) cout << ch << ln;
    // return;
    map<ll, vector<ll>> sweep;
    for (auto [x, y]:pts){
        sweep[x].push_back(y);
    }
    FenwickSick trs(1e10), trb(1e10);
    vector<ll> add;
    for (auto &[x, ys]:sweep){

        sort(ys.begin(), ys.end());
        for (auto y:ys){
            ll val = l-x-y; add.clear();
            trs.collect(y, val, add);
            for (auto ch:add) res.push_back(ch+x+y);
            val = l-x+y; add.clear();
            trb.collect(-y-1, val, add);
            for (auto ch:add) res.push_back(ch+x-y);
        }
        for (ll i=0; i<(ll)ys.size(); i++){
            for (ll j=i-1; j>=0 and ys[i]-ys[j]<=l; j--){
                res.push_back(ys[i]-ys[j]);
            }
        }
        for (auto y:ys){
            trs.add(y, -x-y);
            trb.add(-y, -x+y);
        }
    }
    sort(res.begin(), res.end());
    for (auto ch:res) cout << ch << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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