제출 #1161517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161517		antonn	Road Construction (JOI21_road_construction)	C++20	100 / 100	2434 ms	23848 KiB

road_construction

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 3e5 + 7;

int n, k;
pair<ll, ll> x[N];

ll get(ll d) {
    ll cnt = 0;
    set<pair<ll, int>> s;
    int ptr1 = 1, ptr2 = 1;
    for (int i = 1; i <= n; ++i) {
        while (ptr1 <= n && x[ptr1].F < x[i].F - d) {
            s.erase({x[ptr1].S, ptr1});
            ++ptr1;
        }
        while (ptr2 <= n && x[ptr2].F <= x[i].F + d) {
            s.insert({x[ptr2].S, ptr2});
            ++ptr2;
        }
        
        auto it = s.lower_bound({x[i].S - d, 0});
        while (it != s.end()) {
            if (it->F > x[i].S + d) break;
            ++cnt;
            if (cnt >= 2 * k + n) return k;
            it = next(it);
        }
    }
    return (cnt - n) / 2;
}

ll dist(int i, int j) {
    return max(abs(x[i].F - x[j].F), abs(x[i].S - x[j].S));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> x[i].F >> x[i].S;
    for (int i = 1; i <= n; ++i) x[i] = {x[i].F + x[i].S, x[i].F - x[i].S};
    sort(x + 1, x + n + 1);
    
    ll l = 0, r = 1e10, sol = 0;
    while (l <= r) {
        ll m = (l + r) / 2;
        if (get(m) >= k) {
            sol = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    
    vector<ll> v;
    ll d = sol - 1;
    set<pair<ll, int>> s;
    int ptr1 = 1, ptr2 = 1;
    for (int i = 1; i <= n; ++i) {
        while (ptr1 <= n && x[ptr1].F < x[i].F - d) {
            s.erase({x[ptr1].S, ptr1});
            ++ptr1;
        }
        while (ptr2 <= n && x[ptr2].F <= x[i].F + d) {
            s.insert({x[ptr2].S, ptr2});
            ++ptr2;
        }
        
        auto it = s.lower_bound({x[i].S - d, 0});
        while (it != s.end()) {
            if (it->F > x[i].S + d) break;
            if (it->S < i) v.push_back(dist(i, it->S));
            it = next(it);
        }
    }
    
    while (v.size() < k) v.push_back(sol);
    sort(v.begin(), v.end());
    for (auto i : v) cout << i << "\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