제출 #1169756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169756		SmuggingSpun	Road Construction (JOI21_road_construction)	C++20	7 / 100	9344 ms	104656 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, 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(ll(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);
        int low = 1, high = 2e9, d;
        while(low <= high){
            int mid = (low + high) >> 1LL, 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<int>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(int& x : ans){
            cout << x << "\n";
        }
        for(int i = ans.size(); i < k; i++){
            cout << d << "\n";
        }
    }
}
namespace sub3456{
    const int INF = 2e9 + 1;
    struct Node{
        int cnt, l, r;
        Node(){
            this->cnt = 0;
            this->l = this->r = -1;
        }
    };
    int N_y;
    vector<int>_x(1, -INF), _y(1, -INF);
    vector<Node>st(1, Node());
    void build(int id, int l, int r){
        if(l == r){
            return;
        }
        int m = (l + r) >> 1;
        st[id].l = st.size();
        st.emplace_back(Node());
        st[id].r = st.size();
        st.emplace_back(Node());
        build(st[id].l, l, m);
        build(st[id].r, m + 1, r);
    }
    void update(int id, int l, int r, int p){
        st[id].cnt++;
        if(l == r){
            return;
        }
        int m = (l + r) >> 1;
        if(m < p){
            st.emplace_back(st[st[id].r]);
            st[id].r = int(st.size()) - 1;
            update(st[id].r, m + 1, r, p);
        }
        else{
            st.emplace_back(st[st[id].l]);
            st[id].l = int(st.size()) - 1;
            update(st[id].l, l, m, p);
        }
    }
    int get(int id, int l, int r, int u, int v){
        if(l > v || r < u){
            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){
        minimize(X, ll(INF));
        maximize(X, ll(-INF));
        maximize(yl, ll(-INF));
        minimize(yr, ll(INF));
        return get(upper_bound(_x.begin(), _x.end(), X) - _x.begin() - 1, 0, N_y - 1, lower_bound(_y.begin(), _y.end(), yl) - _y.begin(), upper_bound(_y.begin(), _y.end(), yr) - _y.begin() - 1);
    }
    void solve(){
        for(int i = 1; i <= n; i++){
            _x.emplace_back(x[i] += y[i]);
            _y.emplace_back(y[i] = x[i] - (y[i] << 1LL));
        }
        sort(_x.begin(), _x.end());
        _x.resize(unique(_x.begin(), _x.end()) - _x.begin());
        sort(_y.begin(), _y.end());
        _y.resize(unique(_y.begin(), _y.end()) - _y.begin());
        N_y = _y.size();
        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());
        }
        build(0, 0, N_y - 1);
        int j = 0;
        for(int& i : p){
            if(x[i] != _x[j]){
                j++;
                st[j] = st[j - 1];
            }
            update(j, 0, N_y - 1, lower_bound(_y.begin(), _y.end(), y[i]) - _y.begin());
        }
        ll low = 1, high = LIM, d;
        while(low <= high){
            ll mid = (low + high) >> 1LL;
            int cnt = 0;
            for(int i = 1; i <= n && (cnt >> 1) < k; i++){
                cnt += get(mid + x[i], -mid + y[i], mid + y[i]) - get(-mid - 1 + x[i], -mid + y[i], mid + y[i]) - 1;
            }
            if((cnt >> 1) >= k){
                high = (d = mid) - 1;
            }
            else{
                low = mid + 1;
            }
        }
        set<pair<int, int>>S;
        vector<ll>ans;
        if(d > 1){
            for(int i = 0, j = 0; i < n; i++){
                while(x[p[i]] - x[p[j]] >= d){
                    S.erase(make_pair(y[p[j]], x[p[j]]));
                    j++;
                }
                for(auto it = S.lower_bound(make_pair(y[p[i]] - d + 1, -1)); it != S.end() && (*it).first < y[p[i]] + d; it = next(it)){
                    ans.emplace_back(max(abs(ll(x[p[i]]) - (*it).second), abs(ll(y[p[i]]) - (*it).first)));
                }
                S.emplace(y[p[i]], x[p[i]]);
            }
            sort(ans.begin(), ans.end());
            for(ll& x : ans){
                cout << x << "\n";
            }
        }
        for(int i = ans.size(); i < k; i++){
            cout << d << "\n";
        }
    }
}
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];
    }
    sub3456::solve();
    return 0;
    if(n <= 1000){
        sub1::solve();
    }
    else if(count(y + 1, y + n + 1, 0) == n){
        sub2::solve();
    }
    else{
        sub3456::solve();
    }
}

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

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

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