Submission #1169714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169714		SmuggingSpun	Road Construction (JOI21_road_construction)	C++20	11 / 100	10091 ms	205804 KiB

road_construction

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
const int lim = 25e4 + 5;
const ll LIM = 4e9;
int n, k;
ll x[lim], y[lim];
namespace sub1{
    void solve(){
        vector<ll>a;
        for(int i = 1; i < n; i++){
            for(int j = i + 1; j <= n; j++){
                a.emplace_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
            }
        }
        sort(a.begin(), a.end());
        for(int i = 0; i < k; i++){
            cout << a[i] << "\n";
        }
    }
}
namespace sub2{
    void solve(){
        sort(x + 1, x + n + 1);
        ll low = 1, high = LIM, d;
        while(low <= high){
            ll mid = (low + high) >> 1LL;
            int cnt = 0;
            for(int i = 1, j = 1; i <= n && cnt < k; i++){
                while(x[i] - x[j] > mid){
                    j++;
                }
                cnt += i - j;
            }
            if(cnt >= k){
                high = (d = mid) - 1;
            }
            else{
                low = mid + 1;
            }
        }
        vector<ll>ans;
        for(int i = 1; i <= n; i++){
            for(int j = i - 1; j > 0 && x[i] - x[j] < d; j--){
                ans.emplace_back(x[i] - x[j]);
            }
        }
        sort(ans.begin(), ans.end());
        for(ll& x : ans){
            cout << x << "\n";
        }
        for(int i = ans.size(); i < k; i++){
            cout << d << "\n";
        }
    }
}
namespace sub3456{
    struct Node{
        int cnt, l, r;
        Node(){
            this->cnt = 0;
            this->l = this->r = -1;
        }
    };
    vector<ll>_x(1, -LLONG_MAX);
    vector<Node>st(1, Node());
    void copy_left(int id){
        if(st[id].l == -1){
            st[id].l = st.size();
            st.emplace_back(Node());
        }
        st.emplace_back(st[st[id].l]);
        st[id].l = int(st.size()) - 1;
    }
    void copy_right(int id){
        if(st[id].r == -1){
            st[id].r = st.size();
            st.emplace_back(Node());
            return;
        }
        st.emplace_back(st[st[id].r]);
        st[id].r = int(st.size()) - 1;
    }
    void update(int id, ll l, ll r, ll p){
        if(l == r){
            st[id].cnt++;
            return;
        }
        ll m = (l + r) >> 1;
        if(m < p){
            if(st[id].r == -1){
                st[id].r = st.size();
                st.emplace_back(Node());
            }
            else{
                st.emplace_back(st[st[id].r]);
                st[id].r = int(st.size()) - 1;
            }
            update(st[id].r, m + 1, r, p);
        }
        else{
            if(st[id].l == -1){
                st[id].l = st.size();
                st.emplace_back(Node());
            }
            else{
                st.emplace_back(st[st[id].l]);
                st[id].l = int(st.size()) - 1;
            }
            update(st[id].l, l, m, p);
        }
        st[id].cnt++;
    }
    int get(int id, ll l, ll r, ll u, ll v){
        if(l > v || r < u || id == -1){
            return 0;
        }
        if(u <= l && v >= r){
            return st[id].cnt;
        }
        ll m = (l + r) >> 1LL;
        return get(st[id].l, l, m, u, v) + get(st[id].r, m + 1, r, u, v);
    }
    int get(ll X, ll yl, ll yr){
        maximize(yl, -LIM);
        minimize(yr, LIM);
        return get(upper_bound(_x.begin(), _x.end(), X) - _x.begin() - 1, -LIM, LIM, yl, yr);
    }
    void solve(){
        for(int i = 1; i <= n; i++){
            x[i] += y[i];
            y[i] = x[i] - (y[i] << 1LL);
        }
        for(int i = 1; i <= n; i++){
            _x.emplace_back(x[i]);
        }
        sort(_x.begin(), _x.end());
        _x.resize(unique(_x.begin(), _x.end()) - _x.begin());
        {
            vector<int>p(n);
            iota(p.begin(), p.end(), 1);
            sort(p.begin(), p.end(), [&] (int i, int j){
                return x[i] < x[j];
            });
            for(int i = 1; i < _x.size(); i++){
                st.emplace_back(Node());
            }
            int j = 0;
            for(int& i : p){
                if(x[i] != _x[j]){
                    j++;
                    st[j] = st[j - 1];
                }
                update(j, -LIM, LIM, y[i]);
            }
        }
        ll low = 1, high = LIM, d;
        while(low <= high){
            ll mid = (low + high) >> 1LL, cnt = 0;
            for(int i = 1; i <= n; i++){
                cnt += get(x[i] + mid, y[i] - mid, y[i] + mid) - get(x[i] - mid - 1, y[i] - mid, y[i] + mid);
            }
            if(((cnt - n) >> 1LL) >= k){
                high = (d = mid) - 1;
            }
            else{
                low = mid + 1;
            }
        }
        cout << d;
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
    }
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
    }
    if(n <= 1000){
        sub1::solve();
    }
    else if(count(y + 1, y + n + 1, 0) == n){
        sub2::solve();
    }
    else{
        sub3456::solve();
    }
}

Compilation message (stderr)

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

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