Submission #1079946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079946		nathan4690	Road Construction (JOI21_road_construction)	C++17	38 / 100	10051 ms	49808 KiB

road_construction

// The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
// Spring Training Camp/Qualifying Trial
// March 20–23, 2021 (Komaba, Tokyo)
// Contest Day 2 – Road Construction
// JOI21_road_construction
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pll pair<ll,ll>
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
#define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

struct Segment{
    ll a, b1, b2, sgn, idx;
    Segment(){}
    Segment(ll a, ll b1, ll b2, ll sgn, ll idx): a(a), b1(b1), b2(b2), sgn(sgn), idx(idx){}
    bool operator<(const Segment &rhs) const{
        return a < rhs.a;
    }
};

ll n,k, L, R, mid, cnt[maxn];
pair<ll,ll> p[maxn];
vector<Segment> all;
ordered_set S;

bool check(ll x){
    all.clear();
    f1(i,n){
        cnt[i] = 0;
        all.push_back(Segment(p[i].first - x - 1, p[i].second - x, p[i].second + x, -1, i));
        all.push_back(Segment(p[i].first + x, p[i].second - x, p[i].second + x, 1, i));
    }
    sort(all.begin(), all.end());
    S.clear();
    ll ptr = 1;
    for(Segment item: all){
        while(p[ptr].first <= item.a){
            S.insert({p[ptr].second, ptr});
            ptr++;
        }
        cnt[item.idx] += (S.order_of_key({item.b2, inf}) - S.order_of_key({item.b1, 0})) * item.sgn;
    }
    ll tot = 0;
    f1(i,n) tot += cnt[i];
    tot -= n;
    // cout << x << ' ' << tot;el;
    tot /= 2;
    return tot >= k;
}

set<pair<ll,ll>> S2;
vector<ll> allDist;

void addPath(ll idx1, ll idx2){
    allDist.push_back(max(abs(p[idx1].first - p[idx2].first), abs(p[idx1].second - p[idx2].second)));
}

void getAllLess(ll x){
    S2.clear();
    ll ptr_l = 1, ptr_r = 1;
    f1(i,n){
        ll a1 = p[i].first - x, a2 = p[i].first + x;
        while(p[ptr_r].first <= a2){
            S2.insert({p[ptr_r].second, ptr_r});
            ptr_r++;
        }
        while(p[ptr_l].first < a1){
            S2.erase({p[ptr_l].second, ptr_l});
            ptr_l++;
        }
        ll b1 = p[i].second - x, b2 = p[i].second + x;
        auto it1 = S2.lower_bound({b1, 0});
        auto it2 = S2.lower_bound({b2, inf});
        while(it1 != it2){
            ll idx = (*it1).second;
            if(idx < i) addPath(idx, i);
            it1++;
        }
    }
}

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

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,n) {
        ll x, y;
        cin >> x >> y;
        p[i] = {x-y,x+y};
    }
    p[n+1] = {inf, inf};
    sort(p+1,p+n+1);
    L = 0; R = 4e9;
    while(L <= R){
        mid = (L + R) / 2;
        if(check(mid)) R = mid-1;
        else L = mid+1;
    }
    getAllLess(L-1);
    sort(allDist.begin(), allDist.end());
    for(ll item: allDist) cout << item << '\n';
    for(ll i=allDist.size() + 1;i<=k;i++) cout << L << '\n';
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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