제출 #1079959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079959		nathan4690	Road Construction (JOI21_road_construction)	C++17	65 / 100	10047 ms	52668 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
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;
    }
};

struct FenwickTree{
    int n;
    vector<long long> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0LL){}
    void update(int idx, long long v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    long long getSum(int idx){
        if(idx <= 0) return 0;
        long long res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

ll n,k, L, R, mid, cnt[maxn];
pair<ll,ll> p[maxn];
vector<Segment> all;
vector<ll> values;
FenwickTree fen;

bool check(ll x){
    all.clear();
    values.clear();
    values.push_back(-inf);
    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));
        values.push_back(all.back().b1);
        values.push_back(all.back().b2);
        values.push_back(p[i].second);
    }
    fen = FenwickTree(3*n);
    sort(values.begin(), values.end());
    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});
            ll ptr_x = lower_bound(values.begin(), values.end(), p[ptr].second) - values.begin();
            fen.update(ptr_x, 1);
            ptr++;
        }
        ll ptr_r = lower_bound(values.begin(), values.end(), item.b2) - values.begin();
        ll ptr_l = lower_bound(values.begin(), values.end(), item.b1) - values.begin();
        cnt[item.idx] += (fen.getSum(ptr_r) - fen.getSum(ptr_l - 1)) * 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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